Složitost algoritmu
Z MiS
(Rozdíly mezi verzemi)
m (Přidán odkaz na Algoritmus) |
(→Složitost jako míra pro srovnání algoritmů: Měření složitosti jako samostatná kapitola.) |
||
Řádka 15: | Řádka 15: | ||
* ... | * ... | ||
− | + | ||
− | + | == 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). | |
− | *Zajímá nás maximální nebo průměrná složitost | + | #* 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|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 == | == Asymptotická složitost == |
Verze z 25. 9. 2014, 10:20
Obsah |
Složitost jako míra pro srovnání algoritmů
Hledáme nástroje pro porovnání efektivity algoritmů.
- Máme
N
prvků vstupních dat (N
zá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