Kapitoly
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.
-
01
Proč se počítají operace a ne sekundy
Přirozená otázka zní „jak dlouho to trvá“. Přirozená odpověď — změřit to stopkami — je překvapivě k ničemu, a stojí za to vědět proč.…
-
02
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.…
-
03
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 ros…
-
04
Tři kvadratická třídění a čím se doopravdy liší
Všechna tři jsou O(n²) a přesto se chovají různě. Rozdíl je vidět nejlíp na tom, která část pole je už hotová . Přepínej algoritmus a táhni krokem.…
-
05
Rozděl a panuj: odkud se bere to log n
Kvadratická třídění srovnávají každý prvek skoro s každým. Rychlá třídění dělají něco jiného: rozdělí úlohu na dvě poloviny, vyřeší je zvlášť a výsled…
-
06
Quicksort: pivot rozhoduje o všem
Quicksort vybere jeden prvek — pivot — a přerovná pole tak, aby menší byly vlevo a větší vpravo. Pak totéž na obě poloviny.…
-
07
Konstanta vyhrává na malých datech
Tohle je ta část, kterou O() zahodilo — a ukáže se, že je v praxi rozhodující častěji, než by člověk čekal, protože většina polí, která se v reálném k…
-
08
Vyhledávání a kdy se vyplatí setřídit
Najít hodnotu v neuspořádaném poli znamená projít ho — v průměru půlku, v nejhorším celé.…
-
09
Pole, spojový seznam, hash: tři různé odpovědi
Kontejner se nevybírá podle toho, který je „nejlepší“, ale podle toho, které operace se budou dělat často .…
-
10
Cache: proč je pole rychlejší, než složitost slibuje
Projít pole o milionu prvků je O(n). Projít spojový seznam o milionu prvků je taky O(n).…
-
11
Rozpočet na mikrokontroléru a proč se ve smyčce nealokuje
Na počítači se otázka „je to dost rychlé“ obvykle nepokládá. V regulační smyčce, která má milisekundu na všechno, se pokládá pořád — a dá se na ni odp…
-
12
Kde se to v akademii používá
labka co si odsud bere BitLab Př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.…