O(n): co to říká a co NEŘÍKÁ
Zápis O(n²) říká jednu jedinou věc: jak cena roste, když n roste nade všechny meze. Konstanty se zahazují, nižší členy se zahazují — protože v limitě na nich nezáleží.
Ta věta je užitečná a je pravdivá. Problém je, že se z ní běžně vyvozuje víc, než v ní je.
Čtyři věci, které O() neříká
| otázka | odpověď z O() |
|---|---|
| Jak dlouho to poběží? | vůbec žádná — konstanta se zahodila |
| Který algoritmus je rychlejší při n = 20? | žádná — to je otázka o konstantách, ne o limitě |
| Kolik to sežere paměti? | žádná, dokud se nezapíše zvlášť |
| Chová se to na mém stroji jako v učebnici? | žádná — kapitola 10 |
„Asymptoticky lepší“ a „rychlejší“ nejsou totéž, a rozdíl není teoretický: knihovní třídění ve všech běžných jazycích přepne pod ~16 prvky na třídění vkládáním, protože to kvadratické tam vyhrává. Kdyby O() rozhodovalo, nedělaly by to.
Tři případy, ne jeden
„Quicksort je O(n log n)“ je nepřesné tvrzení, protože nejhorší případ quicksortu je O(n²). Rozlišovat se musí:
- Nejlepší případ — obvykle nezajímavý, protože se na něj nedá spolehnout.
- Průměrný případ — přes jaké rozdělení vstupů? Skutečná data nebývají náhodná.
- Nejhorší případ — jediný, na kterém se dá stavět záruka, a proto jediný, který zajímá regulační smyčku (viz NetLab, kapitola 7 — je to přesně tentýž argument o průměru a ocasu).
A ten nejhorší případ bývá nešťastně obvyklý: quicksort s pivotem na konci má nejhorší případ na už setříděném poli, což je vstup, který v praxi přijde pořád.