Aká je časová zložitosť prioritných frontových operácií v Jave?

Časová zložitosť bežných operácií na „prioritnomqueue“ v Java závisí od konkrétnej operácie. Tu je porucha:

* `Pridať (e e)` / `ponuka (e e)` (vkladanie): O (log n) - Je to preto, že front priority si musí udržiavať svoju vlastnosť haldy, čo si vyžaduje preosievanie nového prvku nahor alebo nadol.

* `remove ()` / `anl ()` (odstránenie prvku najvyššej priority): O (log n) - Odstránenie koreňového prvku (najvyššia priorita) si vyžaduje nahradenie posledným prvkom a potom preosievanie náhradného prvku dole haldy, aby ste obnovili vlastnosť haldy.

* `peek ()` (prístup k prvku najvyššej priority): O (1) - nahliadnutie do prvku najvyššej priority (koreň haldy) je operácia priameho prístupu.

* `Obsahuje (Object O)`: O (n) - Vyžaduje si to iterovanie cez prvky frontu na kontrolu rovnosti. Priority v Java neposkytujú efektívny spôsob kontroly zadržiavania.

* `remove (Object o)`: O (n) - Podobné ako `obsahuje ()`, to zahŕňa iterovanie cez prvky na nájdenie a odstránenie zadaného objektu. Po odstránení objektu sa musí zachovať vlastnosť haldy, ktorá v najhoršom prípade môže trvať čas O (N). (Odstránenie ľubovoľného prvku nie je štandardnou prevádzkou frontov priority a výkon to odráža.)

* `size ()`: O (1) - Veľkosť sa udržiava ako členská premenná, takže prístup k jej konštantnej dobe.

* `isEmpty ()`: O (1) - Jednoducho skontroluje, či je veľkosť 0.

* `clear ()`: O (n) - Odstraňuje všetky prvky z frontu. Zatiaľ čo odstránenie jednotlivých prvkov môže trvať O (log N), vymazanie celej fronty trvá O (n). V niektorých implementáciách to môže byť v skutočnosti implementované ako O (1), iba resetovaním vnútorného poľa a veľkosti.

* `iterator ()`: O (1) - Vráti iterátor pre front priority. Samotný iterátor nie je * usporiadaný * a opakovanie prvkov bude o (n).

Dôležité úvahy:

* `Priorityqueue` je implementovaný ako binárna halda. Štruktúra údajov o halde je to, čo mu dáva logaritmický výkon na vloženie a odstránenie prvku s najvyššou prioritou.

* Porovnávač je rozhodujúci. Porovnávač (alebo prirodzené usporiadanie prvkov, ak nie je poskytnutý žiadny porovnávač) je to, čo určuje prioritu prvkov. Metóda porovnávača „porovnaj ()` musí byť účinná (typicky O (1)) pre celkové operácie frontu priority, aby sa zachovala ich stanovená zložitosť.

* Odstránenie ľubovoľných prvkov (`remove (Object O)`) je neefektívny. Ak často potrebujete odstrániť ľubovoľné prvky z prioritného frontu, zvážte použitie inej dátovej štruktúry alebo kombinácie dátových štruktúr (napr. „Treeset“ kombinovaný s `hashmap` na sledovanie pozícií prvkov). Štandardné fronty priority sú optimalizované pre efektívny prístup k prvku s najvyššou prioritou.

v súhrne:

Kľúčové operácie `add ()` a `remove ()` (z * najvyššieho * prioritného prvku) sú O (log n), čo robí „priorityqueue` veľmi efektívnou voľbou pre scenáre, kde potrebujete udržiavať triedený zber a opakovane pristupovať alebo odstrániť minimálne (alebo maximum, v závislosti od vášho porovnávacieho) prvku.

• Predchádzajúca strana: Aká je syntax na reprezentáciu čísla plávajúceho bodu v Java pomocou plavákového doslovného? 
• Ďalšia strana: No