Dominik Farhan

Dolní odhady na binární vyhledávání a na třídění porovnávacími algoritmy

Jedinou povolenou operací je porovnávání. Objekty můžeme vidět jako černé skříňky. Nezajímá nás, o co jde, ale potřebujeme je umět porovnávat. Čas bude záviset na počtu porovnání.

Rozhodovací strom

Na porovnávací algoritmus se lze dívat jako na strom, který zaznamenává všechna možná porovnání a jejich výsledky.

Každý z možných průběhů algoritmu koresponduje jedné cestě z kořene do listu. Počet provedených operacích je pak roven počtu vrcholů, kterými jsme prošli. V nejhorším případě tedy hloubce stromu.

Binární vyhledávání

Věta. Rozhodovací strom binárního vyhledávání bude mít alespoň logaritmickou hloubku.
Důkaz. Máme jistě alespoň nn možných odpovědí. Víme, že rozhodovací strom je binární. Binární strom na nn vrcholech má hloubku alespoň log⁡n\log n. Hotovo :).

Třídění

Věta. Třídění v porovnávacím modelu potřebuje alespoň Ω(nlog⁡n)\Omega(n \log n) času.
Důkaz.

Rozhodovací strom třídění je binární. V každém listu je nějaká permutace vstupních prvků. Těchto permutací je celkem n!n!. Výška tedy bude alespoň log⁡n!\log n!.

Teď už jsou to jen úpravy.

log⁡n!=∑i=1nlog⁡i≥∑i=n/2nlog⁡i≥∑i=n/2nlog⁡n/2=∑i=n/2nlog⁡n−1=n/2log⁡n−n/2=Ω(nlog⁡n)\log n! = \sum_{i=1}^n \log i \geq \sum_{i=n/2}^n \log i \geq \sum_{i=n/2}^n \log n/2 = \sum_{i=n/2}^n \log n-1 = n/2 \log n - n/2 = \Omega(n \log n)

Případně použijeme Stirlingovu formuli n!≈2πn(n/e)nn! \approx \sqrt{2\pi n}(n/e)^n

Pěkně je vše popsané zde.