Dolní odhad složitosti problému třídění

Algoritmy Třídění Dolní odhad složitosti problému třídění

Každý, kdo se setkal s alespoň dvěma třídícími algoritmy, si jistě položil otázku, jestli může existovat algoritmus, který to udělá rychleji. A tím rychleji mám na mysli z hlediska (asymptotické) časové složitosti, tedy zda existuje kategoricky efektivnější algoritmus. Složitostí problému (nikoli složitostí algoritmu) je tedy myšlena složitost úlohy, tedy složitost nejlepšího možného algoritmu, který úlohu vyřeší. V některých případech algoritmus dokonce nemusí být ani známý, ale my budeme vědět, že existuje a že bude někdy objeven. Teď se zaměříme na problém třídění prvků.

Každý zde uvedený algoritmus nám dávál vlastně horní odhad složitosti problému třídění. Bubblesort měl časovou složitost O(n2), věděli jsme tedy, že třídit můžeme nejhůře s touto složitostí. Např. Heap sort však ten samý problém zvládl s časovou složitostí O(n log n). Automaticky víme, že to půjde nejhůře takto. Ale může existovat algoritmus s ještě lepší časovou složitostí? Budeme předpokládat, že ne a toto tvrzení se pokusíme dokázat. Dokazujeme tedy dolní složitost problému třídění, tedy že to nejde lépe než v O(n log n).

Důkaz

Pokud třídíme na základě porovnávání prvků (pro dvojice prvků určujeme, který je větší, resp. menší), můžeme každý takový algoritmus zapsat jako rozhodovací strom. Rozhodovací strom je binární strom, který ve vnitřních vrcholech obsahuje dvojice porovnávaných prvků a v listech jejich permutace. V každém listu je tedy uložen jeden možný výstup algoritmu, ve všech listech jsou potom všechny možnosti, jak mohou být prvky v poli seřazené.

Takový rozhodovací strom pro pole 2 prvků by byl jednoduchý, obsahoval by jen kořen, ve kterém bychom se zeptali: je a < b? Pokud ano, dostali bychom permutaci [a, b]. Pokud ne, dostali bychom [b, a] a bylo by setříděno. Rozhodovací strom však s přibývajícími prvky velmi rychle roste. Takhle by vypadal rozhodovací strom pro 3 prvky:

Rozhodovací strom pro 3 prvky

Pro 4 prvky by byl strom asi 4x větší.

Pokud třídíme n prvků, všech permutací těchto prvku bude celkem zcela jistě n!, strom tedy musí mít nejméně n! listů. Stromy hloupějších algoritmů jich budou mít mnohem více. Můžeme si představit, že ten úplně nejlepší algoritmus má ideální strom s n! listy. V nejhorším případě (když půjde po nejdelší větvi) při průchodu od kořene do listu udělá tolik porovnání, kolik má strom "úrovní", tedy jaká je výška stromu h.

Binární strom výšky h bude jistě obsahovat max. 2^h listů.

Počet listů binárního stromu výšky h

Jak jsem se zmínil výše, listů musí být nejméně n!, aby byl strom úplný, jinak by nějakou permutaci vstupních prvků nedokázal setřídit. Budeme tedy vycházet z nerovnice:

Po zlogaritmování dostaneme:

Nyní se podrobně zaměřme pouze na n! a na to, zda bychom ho nemohli pro naše potřeby nějak upravit. K dalším krokům by se nám velmi hodilo dostat místo n! výraz (n/2)^(n/2). Toho dosáhneme následujícím trikem:
Pro lepší představu jsem na ukázku přidal členy 8!. n! si můžeme rozepsat jako:

Jelikož v naší původní nerovnici bylo >= n!, můžeme si klidně dovolit n! zmenšit a nerovnost neporušíme. Vezmeme si tedy jen levou polovinu ze zápisu výše a tu pravou zahodíme.

Můžeme si dokonce dovolit nahradit všechny členy za n/2, protože každý člen je jistě >= n/2, nerovnost tedy opět neporušíme.

Výše uvedený výraz můžeme zapsat jako (n/2)^(n/2) a dosadit do původní nerovnice.

Upravujeme:

(mocnina šla před logaritmus, log. podílu je rozdíl logaritmů, log 2 je 1, tu zanedbám a zvýším jmenovatel). Dostáváme tedy h >= n/4 log n.

Což znamená, že každý algoritmus musí v nejlepším případě udělat porovnání (konstantu jsme schovali do symbolu Omega)

Dolní odhad složitosti problému třídění je a tedy nemůže existovat třídící algoritmus založený na vzájmeném porovnávání prvků s lepší časovou složitostí než touto. Všimněte si, že jsem zdůraznil založený na vzájmeném porovnávání prvků. Že by to přeci jen šlo rychleji? O tom je následující článek - Counting sort :)


 

  Aktivity (2)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!


 


Miniatura
Předchozí článek
Quick sort
Miniatura
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Counting sort

 

 

Komentáře

Avatar
tonislav.strnad:

ahoj, ja jsem trochu zmatenej
kdyz si za n dosadim 4. n! je mensi nez n/2 * n/2 (n/2krát) tak

4! není menší než 2*2 .
:(

 
Odpovědět 25.10.2012 12:26
Avatar
matesax
Redaktor
Avatar
Odpovídá na tonislav.strnad
matesax:

Je to nekonečná řada...

 
Odpovědět 25.10.2012 12:50
Avatar
Kit
Redaktor
Avatar
Kit:

Ještě bys mohl napsat článek o odhad složitosti problému řazení, protože třídění se dělá jen výjimečně, ale řazení se dělá velmi často.

Odpovědět  -1 25.10.2012 18:25
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
trantanh
Člen
Avatar
trantanh:

nemáš náhodou ten obrázek špatně popsány?

 
Odpovědět 3.5.2015 20:44
Avatar
mochhito
Člen
Avatar
mochhito:

Ahoj, tu nerovnost mas naopak.
(vid obrazok)

 
Odpovědět 16.6.2015 13:36
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.