Mým úkolem bylo zaměřit se na rozhodovací strom jako na datovou strukturu, která slouží k odhadnutí časové složitosti různých algoritmů, především však třídění založeného na porovnávání prvků. Ukážu, že složitost tohoto třídění je stejná jako hloubka rozhodovacího stromu, který danému úkolu odpovídá, a určíme, jaká je hloubka tohoto stromu v nejhorším a průměrném případě.
Nejprve je třeba si ukázat, co to vlastně rozhodovací strom je. Vezměme si tedy pro názornost zmíněný problém třídění. Pokud jedinou operací, kterou můžeme na klíčích porovnávaných prvků provádět, je porovnání, potom celý postup algoritmu je vlastně posloupnost porovnávání prvků a podle výsledku porovnání se rozhodneme, jak pokračovat dál, tedy které prvky budeme porovnávat dál. Algoritmus tedy postupuje po binárním stromě z kořene, přičemž podle výsledku porovnání v každém vnitřním vrcholu se rozhodne zda pokračovat vpravo či vlevo. Pokud se na tento strom podíváme blíže, vidíme, že každý vnitřní vrchol obsahuje dva prvky z posloupnosti, kterou chceme setřídit, a pokud je větší první prvek, pokračuje algoritmus pravým synem, v opačném případě vstoupí do svého levého následníka.Z tohoto popisu je již zřejmá následující definice.
Definice:Rozhodovací strom je binární strom, jehož vnitřní vrcholy mají názvy typu Si: Sj, a hrany vycházející z těchto vrcholů mají označení > a <=.
Mějme nyní S1, ....., Sn prvky univerza U. Jak nyní bude vypadat rozhodovací strom, který řeší problém setřídění této posloupnosti?
Definice: Mějme rozhodovací strom T. Řekneme, že T řeší problém setřídění velikosti n, pokud existuje označení listů T permutacemi {1,...., n} takové, že pro každý vstup S1, ...., Sn prvků univerza U platí, že jestliže list, ve kterém výpočet pro tuto posloupnost skončí, má označení p, tak potom Sp(1) <= Sp(2) <= ....... <= Sp(n).
Nyní se můžeme podívat, jak je to se složitostí třídění v nejhorším a v průměrném případě. Nechť pro rozhodovací strom T a permutaci p je l(T, p) hloubka listu, ve kterém skončí výpočet pro posloupnost S1, ....., Sn, kde Sp(1) < Sp(2) < ....... < Sp(n). Definujme
S(n) = min max l(T, p) T p
kde T prochází přes všechny rozhodovací strom řešící problém třídění a p přes všechny permutace. l(T, p) přesně odpovídá počtu porovnání pro daný strom T a permutaci vstupů, maximum přes všechny permutace tedy vybere složitost v nejhorším případě pro daný algoritmus.Minimalizací přes T potom vybereme algoritmus, který má v nejhorším případě nejmenší složitost. Tedy S(n) udává minimální složitost, jakou může libovolný třídící algoritmus dosáhnout v nejhorším případě. Nyní se pokusím spočítat nějaké omezení pro S(n).
Je jasné, jaký je horní odhad.Protože jsme S(n) počítali jako minimum přes všechny rozhodovací stromy řešící problém třídění, jakýkoli algoritmus, založený na porovnávání, který dokáže setřídit vstupní posloupnost, nám svou složitostí v nejhorším případě dává horní odhad na S(n). Známé třídící třídící algoritmy jako např. Heapsort nebo Mergesort dosahují v nejhorším případě složitost O(n.log(n)).Proto platí také
S(n) = O(n.log n)
Nyní předpokládejme, že S(n) <= k. Binární strom s hloubkou <= k má nejvýše 2k listů. Naopak rozhodovací strom řešící problém třídění velikosti n musí mít alespoň n! listů, aby mohl postihnout všechny možnosti permutací vstupní posloupnosti. Tedy musí platit
2S(n) >= n! neboli S(n) >= log n!
Pomocí jednoduché aproximace faktoriálu
n! >= nn/2
dostáváme, že
S(n) >= (n/2) . log n
Tedy pro problém složitosti třídění v nejhorším případě platí
S(n) = Theta(n . log n)
Důsledkem tohoto je, že nelze sestrojit třídící algoritmus založený na porovnání, který by dokázal setřídit posloupnost v nejhorším případě v čase menším než n . log(n).
Pokud bychom chtěli přesněji spočítat složitost nejlepšího hypotetického třídícího algoritmu v nejhorším případě, použijeme Stirlingův vzorec pro aproximaci n! a dostaneme
S(n) >= log n! = (n + 1/2) log n - n/ loge2 + O(1) = n log(n) - 1.43 n + O(log n)
Nyní definujme
A(n) = min 1/n! sum l(T, p) T p
Výraz l(T, p) opět znamená hloubku listu s označením p ve stromu T. Zde tedy počítáme minimum přes všechny rozhodovací stromy řešící problém třídění z hodnoty průměrné hloubky listu, který může být dosažen při výpočtu algoritmu. Protože průměrná hloubka listu ve stromu s k listy je stejná pro všechny stromy, vezmu si strom, který má své listy tak, že jejich hloubka se pro libovolné dva listy liší pouze o 1. Takový strom má hloubku >= log n!. To zůstane zachováno i pokud vezmeme minimu přes všechny takové stromy. Tedy
A(n) >= log n!
Podobným odhadem jako v nejhorším případě dostáváme
A(n) >= n log n
Závěr: Každý rozhodovací strom řešící problém třídění potřebuje alespoň horní celou část z log n! porovnání v nejhorším případě i v průměru.
Pomocí tohoto závěru ukážu ještě složitost jednoho algoritmu, který se řeší pomocí rozhodovacího stromu.Jde o problém jedinečnosti prvků.Máme n prvků S1, ......, Sn z univerza U a pomocí porovnání máme rozhodnout, zda platí, že Si <> Sj pro každé i <> j.Budu chtít ukázat, že každý rozhodovací strom řešící problém jedinečnosti provede v nejhorším případě alespoň log n! porovnání.
K tomuto závěru dojdeme tak, že ukážu, že každý rozhodovací strom řešící problém jedinečnosti řeší také problém třídění. Nechť tedy T je rozhodovací strom řešící problém jedinečnosti velikosti n, jeho vnitřní vrcholy jsou označeny Si : Sj a listy jsou označeny 'ano' nebo 'ne'. Pokud výpočet skončí v listu označeném 'ano!, pak platí Si <> Sj pro každé i <> j, jinak ne.
Nyní pro permutaci p o n prvcích označím v(p) ten list, kterým skončí výpočet při vstupu S1, ......, Sn, takže Sp(1) < Sp(2) < ....... < Sp(n). Ten je jednoznačně definován, protože výpočet pro jakýkoli vstup takový, že Sp(1) < Sp(2) < ....... < Sp(n), skončí ve stejném listu. Nyní stačí dokázat následující lemma.
Lemma: v(p) <> v(q) pro p <> q.
Důkaz: Sporem. Nechť existují permutace p, q takové, že v(p) == v(q)
a přitom p <> q. List v(p) je označen 'ano', protože mezi prvky platí
ostré nerovnosti. Zkonstruujeme vstup S1, ......, Sn
takový, že výpočet nad tímto vstupen skončí ve v(p) a přitom Si =
Sj pro i <> j.
Nechť u1,......, uk
je posloupnost vnitřních vrcholů na cestě z kořene do listu v(p). Na našem
konstruovaném vstupu S1, ......, Sn definujme částečné
uspořádání P takové, že když ul je označeno Si :
Sj, potom relaci mezi Si a Sj definujme tak,
aby sledovala cestu do v(p). P je potom nejmenší uspořádání respektující toto
pravidlo. Každý vstup R1, ......, Rn, který splňuje
Ro(1) < Ro(2) < ....... < Ro(n) pro
o = p nebo o = q, splňuje také částečné uspořádání P.Protože p <> q,
není P lineární, a proto existují i <> j takové, že Si a
Sj nejsou uspořádány P. Vezměme si tedy vstup S1,
......, Sn splňující P a Si = Sj. Výpočet nad
tímto vstupen skončí ve v(p) a dá tedy výsledek 'ano', což je spor pro i, j.
Hybridsort je jednoduchý algoritmus, který není založen pouze na porovnání, a proto může dosahovat lepší složitosti než O(n log n). Tedy daří se mu to alespoň v průměrném případě. Je vlastně kombinací dvou třídících algoritmů, Bucketsortu, který má sice lineární časovou složitost i v nejhorším případě, ale má dost omezeno vsupní univerzum ( typicky na interval přirozených čísel), a Heapsortu. Touto kombinací se dosahuje toho, že algoritmus můžeme použít k třídění reálných čísel a přitom dosahuje lineární složitosti v průměrném případě.
Mějme tedy pro jednoduchost vstupní posloupnost čísel xi, 0 <= xi <= 1, 1 <= i <= n. Dále mějme pevné reálné číslo a a k je rovno an. Algoritmus sám je velice jednoduchý.
Správnost algoritmu je zřejmá, rozdělení do zásuvek jistě zachová uspořádání a o korektnosti Heapsortu snad nikdo nepochybuje.
Tvrzení 1: V nejhorším případě má algoritmus složitost O(n log n).
Důkaz: První fáze jistě proběhne lineárně. Nechť po jejím skončení označuje ti počet prvků v i-té zásuvce. Potom složitost druhé fáze je
O( sum ti log ti) i
přičemž
0 . log 0 = 0 sum ti = n i
Potom tedy
sum ti log ti <= sum ti log n = n log n i i
Tvrzení 2: Pokud jsou xi volena z [0, 1] se stejnou pravděpodobností, potom očekávaný čas výpočtu algoritmu je O(n).
Důkaz: Nechť ti je počet prvků v i-té zásuvce po první fázi. Potom pravděpodobnost P( ti = h) = (nh) (1/k)h(1 - 1/k)n - h, protože xj je v i-té zásuvce s pravděpodobností 1/k. Očekávaný čas druhé fáze tedy je
k n E( sum ti log ti) = k . sum (h . log h) (nh)(1/k)h(1 - 1/k)n - h i=1 h=2 n <= k . sum h2 (nh)(1/k)h(1 - 1/k)n - h h=2 = k (n (n - 1) / k2 + n/k) = O(n)