←
AlgoLab operace, ne sekundy
Otevřít interaktivní verzi → Do kalkulačky →

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Pod tím leží

Kde se to v akademii používá

labkaco si odsud bere
BitLabPřetečení u (lo + hi) / 2 v binárním vyhledávání je jeho kapitola 4 — chyba, která byla v knihovně Javy devět let.
NetLabTentýž argument o nejhorším případě proti průměru, jen na síti místo na algoritmu. Kapitola 11 tady a kapitola 8 tam říkají doslova totéž.
ControlLabRegulátor na mikrokontroléru má rozpočet v taktech. Kapitola 11 říká, kolik se do něj vejde — a proč se v něm nealokuje.
FilterLabMedián z okna je třídění na malém poli — a je to přesně ten případ z kapitoly 7, kde vyhrává „pomalejší“ algoritmus.
OptiLabPočet iterací je tam totéž, co je tady počet operací: měřitelná veličina, kterou se metody porovnávají.
MatrixLabPrůchod maticí po řádcích proti sloupcům je kapitola 10 — stejný počet operací, jiná lokalita.

Co si odnést

  1. Počítat operace, ne sekundy. Naměřená milisekunda se při druhém spuštění liší; počet porovnání je stejný navždycky, a dá se o něm tvrdit přesná věc.
  2. O() říká, jak to roste — nic víc. Neříká jak dlouho, neříká co vyhraje při n = 20 a neříká nic o paměti ani o cache.
  3. Nejhorší případ bývá nešťastně obvyklý. Quicksort s pivotem na konci má nejhorší případ na už setříděném poli, a rekurze mu jde n úrovní hluboko.
  4. Konstanta vyhrává na malých datech, a proto knihovní sorty pod ~16 prvky přepínají na třídění vkládáním.
  5. Setřídit kvůli jednomu hledání se nevyplatí. Hranice je u n = 1000 kolem osmnácti hledání.
  6. Cache vysvětlí to, co složitost neřekne. Průchod polem a seznamem je O(n) obojí, a pole sáhne do paměti osmkrát méně často.
  7. V reálném čase je předvídatelnost víc než rychlost. Nealokovat, omezit rekurzi, znát nejhorší případ — a je to tentýž závěr, ke kterému došel NetLab o síti.