Složitost algoritmu
Z MiS
Obsah |
Složitost jako míra pro srovnání algoritmů
Hledáme nástroje pro porovnání efektivity algoritmů.
- Máme
Nprvků vstupních dat (Nzákazníků,Nčísel,...), - zajímá nás, který ze dvou algoritmů vrátí výsledek dříve.
Rychlejší algoritmus → lepší algoritmus!
- Problém — čas je ovlivněn
- volbou konkrétního zadání stejného problému,
- výkonem počítače (pozor také na další běžící procesy),
- kvalitou implementace algoritmu,
- použitým programovacím jazykem,
- použitými knihovnami,
- ...
Měření složitosti
- Neměříme čas, ale počet operací!
- Tím omezíme vliv konkrétního HW.
- Nepočítáme všechny dílčí operace!
- Obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk).
- Tím eliminujeme vliv použitého překladače, knihoven, jazyka, procesorové architektury,...
- Zajímají nás velká data, řádový růst!
- Viz asymptotická složitost.
- Malé instance skončí v rozumném čase, i když se budou počítat neefektivně.
- Zajímá nás maximální nebo průměrná složitost!
- Tím eliminujeme vliv konkrétního zadání.
Asymptotická složitost
- Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat.
- Zapisujeme
O(f(N))- N... velikost dat
- f(N)... funkce, jejímž růstem lze limitovat růst počtu operací
- Pokud je velikost vstupu N, pak je složitost limitována funkcí
A+B.f(N)
- Příklady růstu počtu operací
- O(N) — lineární
- Lepší než lineární
- O(log(N))
- O(sqrt(N))
- O(N.log(N))
- O(N2) — kvadratický
- O(N3) — kubický
- Polynomiální
- roste jako libovolný polynom (omezen O(Ni), kde i je lib. konstanta).
- O(2N) — exponenciální
- Viz například: Hanoiské věže.
- Úkol — Navrhněte algoritmus a odhadněte složitost
- Hledání maxima
Související pojmy
- Složitost problému
- Složitost nejlepšího algoritmu, který řeší daný problém.
- × složitost nejlepšího známého algoritmu.
- Maximální × průměrná složitost
- viz QuickSort
- Aneb: Pojedete do školy o 4 hodiny později proto, že v nejhorším možném případě Vám cesta bude trvat pěšky 4 hodiny?
- Paměťová × časová složitost
