Změřený růst proti předpovědi
„Tohle je kvadratické“ je tvrzení, které jde ověřit. Stačí spustit algoritmus na několika velikostech, spočítat operace a podívat se, jak ta čísla rostou.
Proč logaritmické osy
Když je počet operací c·n^k, pak po zlogaritmování obou stran vyjde přímka:
Sklon té přímky je přímo ten exponent. Konstanta c jen posune přímku nahoru nebo dolů a sklon nezmění — a to je přesně to, co O() zahazuje. Na log-log grafu je tedy vidět obojí naráz: sklon je složitost, výška je konstanta.
Co vyjde
| algoritmus | změřený sklon | teorie |
|---|---|---|
| bublinkové | 2,01 | n² |
| vkládáním | 1,96 | n² |
| výběrem | 1,98 | n² |
| slučováním | 1,22 | n log n |
| quicksort | 1,23 | n log n |
Ta 1,22 u n log n stojí za vysvětlení, protože vypadá jako nepřesnost a není. n log n není mocninná závislost — na log-log osách to není přímka, jen skoro. Proložený sklon proto vyjde mezi 1 a 2 a pomalu roste s rozsahem n, na kterém se měří. To není chyba měření; je to důkaz, že ta funkce mocninná není.
Nejlepší případ se taky změří
Na už setříděném poli se třídění vkládáním i bublinkové zlomí na lineární — změřený sklon spadne na 1,0. Třídění výběrem ne: to zůstane na 2,0, protože nemá jak poznat, že je hotovo. Prochází celý zbytek pole i tehdy, když je celé setříděné.
To je nejnázornější ukázka toho, že „stejná složitost“ neznamená „stejné chování“. Tři kvadratické algoritmy, a na setříděném vstupu jsou dva z nich lineární a třetí ne.