Dolný odhad zložitosti problému triedenia

Každý, kto sa stretol s aspoň dvoma triediacimi algoritmy, si iste položil otázku, či môže existovať algoritmus, ktorý to urobí rýchlejšie. A tým rýchlejšie mám na mysli z hľadiska (asymptotickej) časovej zložitosti, teda či existuje kategoricky efektívnejší algoritmus. Zložitosťou problému (nie zložitosťou algoritmu) je teda myslená zložitosť úlohy, teda zložitosť najlepšieho možného algoritmu, ktorý úlohu vyrieši. V niektorých prípadoch algoritmus dokonca nemusí byť ani známy, ale my budeme vedieť, že existuje a že bude niekedy objavený. Teraz sa zameriame na problém triedenie prvkov.

Každý tu uvedený algoritmus nám dávali vlastne horný odhad zložitosti problému triedenia. Bubblesort mal časovú zložitosť O (n ^2), vedeli sme teda, že triediť môžeme najhoršie s touto zložitosťou. Napr. Heap sort však ten istý problém zvládol s časovou zložitosťou O (n log n). Automaticky vieme, že to pôjde najhoršie takto. Ale môže existovať algoritmus s ešte lepšou časovou zložitosťou? Budeme predpokladať, že nie a toto tvrdenie sa pokúsime dokázať. Dokazujeme teda dolná zložitosť problému triedenia, teda že to nejde lepšie ako v O (n log n).

Dôkaz

Ak triedime na základe porovnávania prvkov (pre dvojice prvkov určujeme, ktorý je väčší, resp. Menší), môžeme každý takýto algoritmus zapísať ako rozhodovací strom. Rozhodovací strom je binárny strom, ktorý vo vnútorných vrcholoch obsahuje dvojice porovnávaných prvkov a v listoch ich permutácie. V každom liste je teda uložený jeden možný výstup algoritmu, vo všetkých listoch sú potom všetky možnosti, ako môžu byť prvky v poli zoradené.

Takýto rozhodovací strom pre pole 2 prvkov by bol jednoduchý, obsahoval by len koreň, v ktorom by sme sa spýtali: je a <b? Ak áno, dostali by sme permutáciu [a, b]. Ak nie, dostali by sme [b, a] a bolo by zotriedené. Rozhodovací strom však s pribúdajúcimi prvkami veľmi rýchlo rastie. Takto by vyzeral rozhodovací strom pre 3 prvky:

Pre 4 prvky by bol strom asi 4x väčšie.

Ak triedime n prvkov, všetkých permutácií týchto prvku bude celkom určite n !, strom teda musí mať najmenej n! listov. Stromy hlúpejší algoritmov ich budú mať oveľa viac. Môžeme si predstaviť, že ten úplne najlepší algoritmus má ideálne strom sn! listy. V najhoršom prípade (ak pôjde po najdlhšej vetve) pri priechode od koreňa do listu urobí toľko nákupný, koľko má strom "úroveň", teda aká je výška stromu h.

Binárne strom výšky h bude určite obsahovať max. 2 ^ h listov.

Ako som spomenul vyššie, listov musí byť najmenej n !, aby bol strom úplný, inak by nejakú permutáciu vstupných prvkov nedokázal zotrieďiť. Budeme teda vychádzať z nerovnice:

Po zlogaritmování dostaneme:

Teraz sa podrobne zamerajme iba na n! a na to, či by sme ho nemohli pre naše potreby nejako upraviť. K ďalším krokom by sa nám veľmi hodilo dostať miesto n! výraz (n / 2) ^ (n / 2). To dosiahneme nasledujúcim trikom:
Pre lepšiu predstavu som na ukážku pridal členmi 8 !. n! si môžeme rozpísať ako:

Keďže v našej pôvodnej nerovnicu bolo> = n !, môžeme si pokojne dovoliť n! zmenšiť a nerovnosť neporušíme. Vezmeme si teda len ľavú polovicu zo zápisu vyššie a tú pravú zahodíme.

Môžeme si dokonca dovoliť nahradiť všetky členmi za n / 2, pretože každý člen je určite> = n / 2, nerovnosť teda opäť neporušíme.

Vyššie uvedený výraz môžeme zapísať ako (n / 2) ^ (n / 2) a dosadiť do pôvodnej nerovnice.

upravujeme:

(Mocnina išla pred logaritmus, log. Podielu je rozdiel logaritmov, log 2 je 1, tú zanedbáme a zvýšim menovateľ). Dostávame teda h> = n / 4 log n.

Čo znamená, že každý algoritmus musí v najlepšom prípade urobiť
nákupný (konštantu sme schovali do symbolu Omega)

Dolné odhad zložitosti problému triedenie je
a teda nemôže existovať triediace algoritmus založený na základe spoločnej porovnávanie prvkov s lepšou časovou zložitosťou než touto. Všimnite si, že som zdôraznil založený na základe spoločnej porovnávanie prvkov. Že by to predsa len išlo rýchlejšie? O tom je nasledujúci článok - Counting sort