Aká je časová zložitosť vyskočenia prvku z prioritného frontu?

Časová zložitosť praskania (odstránenie prvku s najvyššou prioritou) z prioritného frontu závisí od základnej implementácie frontu priorít. Tu je rozdelenie bežných implementácií:

* binárna halda:

* o (log n) . Toto je najbežnejšia a efektívnejšia implementácia. Odstránenie koreňa (prvok s najvyššou prioritou) trvá O (1). Potom však musíte nahradiť koreň za posledný prvok v halde a „Heapify Down“, aby ste obnovili vlastnosť haldy. Táto operácia Heapify trvá O (log n) čas, kde n je počet prvkov v halde.

* Binárny strom vyhľadávania (BST):

* o (log n) v priemernom prípade vyváženého BST (ako strom AVL alebo červeno-čierny strom). Nájdenie maximálneho (alebo minima, v závislosti od priority) je O (log N) a jeho odstránenie je tiež O (log N).

* o (n) v najhoršom prípade pre nevyvážený BST. Ak je strom skreslený (napr. Pripomína prepojený zoznam), nájdenie a odstránenie maxima/minimum môže trvať lineárny čas.

* pole alebo prepojený zoznam (nevyrovnané):

* o (n) . Musíte iterovať celý zoznam, aby ste našli prvok s najvyššou prioritou a potom ho odstránili.

* pole alebo prepojený zoznam (usporiadaný):

* Ak je objednané podľa priority (napr. Zoradené pole):Vyskočenie prvku s najvyššou prioritou (pravdepodobne na konci alebo na začiatku, v závislosti od objednávania) môže byť O (1). Ak však používate triedené pole a potrebujete zachovať triedené poradie po odstránení prvku, možno budete potrebovať posunutie prvkov, čo vedie k O (N) v najhoršom prípade. Prepojené zoznamy sa môžu vyhnúť posunutiu, takže praskanie je O (1) Ak viete, kde je prvok s najvyššou prioritou, ale zistenie, že ešte začína (n).

* fibonacci halda:

* o (log n) amortizovaný čas. Haldy Fibonacci sú na implementáciu zložitejšie, ale ponúkajú teoreticky lepší výkon pre určité operácie, najmä ak máte veľa operácií „zníženia kľúča“. „Amortizované“ znamená, že zatiaľ čo individuálne operácie môžu trvať dlhšie, priemerná časová zložitosť v sekvencii operácií je O (log N).

Zhrnutie:

| Implementácia Časová zložitosť (praskanie)

| ------------------- | ----------------------- |

| Binárna halda O (log n) |

| Vyvážený BST O (log n) |

| Nevyvážený BST O (n) |

| Neživotné pole/Zoznam O (n) |

| Objednané pole/zoznam | O (1) alebo O (n) |

| Fibonacci Halda | O (log n) (amortizované)

V praxi:

Najbežnejšou implementáciou pre prioritné fronty je binárna halda , Kvôli jeho dobrému výkonu (O (log N)) a relatívne jednoduchej implementácii. Preto môžete vo všeobecnosti predpokladať, že časová zložitosť vyskočenia z prioritného frontu bude o (log n) Pokiaľ dokumentácia alebo kontext výslovne neuvádza inú základnú dátovú štruktúru.

• Predchádzajúca strana: Aká je časová zložitosť algoritmu Quicksort z hľadiska veľkej notácie? 
• Ďalšia strana: Aká je časová zložitosť algoritmu Quicksort?