Složitost algoritmu
Z MiS
(Rozdíly mezi verzemi)
m (→Asymptotická složitost: Oprava vzhledu) |
m (Přidáno upozornění na omezení kapacity paměti.) |
||
| Řádka 6: | Řádka 6: | ||
*zajímá nás, který ze dvou algoritmů vrátí výsledek dříve. | *zajímá nás, který ze dvou algoritmů vrátí výsledek dříve. | ||
<div class="Poznamka">Rychlejší algoritmus → lepší algoritmus!</div> | <div class="Poznamka">Rychlejší algoritmus → lepší algoritmus!</div> | ||
| + | <div class="Varovani">Má to ale jeden háček — musí nám stačit systémové prostředky pro daný algoritmus, zejména operační paměť. ;)</div> | ||
;Problém — čas je ovlivněn: | ;Problém — čas je ovlivněn: | ||
| Řádka 27: | Řádka 28: | ||
# ''Zajímá nás maximální nebo průměrná složitost!'' | # ''Zajímá nás maximální nebo průměrná složitost!'' | ||
#* Tím eliminujeme vliv konkrétního zadání. | #* Tím eliminujeme vliv konkrétního zadání. | ||
| + | #* Viz [[#Maximální a průměrná složitost|průměrná složitost]]. | ||
| + | |||
== Asymptotická složitost == | == Asymptotická složitost == | ||
| Řádka 51: | Řádka 54: | ||
* Hledání maxima | * Hledání maxima | ||
</div> | </div> | ||
| + | |||
| + | |||
| + | == Maximální a průměrná složitost == | ||
| + | * Počet vykonaných operací se může lišit podle podoby konkrétních dat. | ||
| + | * Třeba při řazení podle abecedy může být počet operací jiný pro ''téměř setříděná'' data a jiná pro data, která jsou úplně přeházená. | ||
| + | * Některé algoritmy mohou mít velmi dobré chování ve většině případů, ale pro nešťastně uspořádaná data mohou mít složitost větší. (Viz třeba známý řadící algoritmus ''QuickSort''.) | ||
| + | |||
| + | <div class="Priklad"> | ||
| + | * Při cestě do školy vstanu tak, abych v průměrném případě dorazil včas. Pokud dojde k nehodě na silnici, může se stát, že se zpozdím. Ale je to málo pravděpodobné a vyrážet o hodinu dříve pro případ nehody by bylo nepraktické — řeším ''průměrnou'' délku cesty. | ||
| + | * Na druhou stranu pokud jdu k maturitě, čtvrthodinové zpoždění by znamenalo, že budu muset maturovat až na podzim a proto raději hodinu počkám — zajímá mě spíše délka cesty ''v nejhorším případě''. | ||
| + | </div> | ||
| + | |||
== Související pojmy == | == Související pojmy == | ||
| Řádka 56: | Řádka 71: | ||
*Složitost nejlepšího algoritmu, který řeší daný problém. | *Složitost nejlepšího algoritmu, který řeší daný problém. | ||
*× složitost nejlepšího ''známého'' algoritmu. | *× složitost nejlepšího ''známého'' algoritmu. | ||
| − | |||
| − | |||
| − | |||
| − | |||
; Paměťová × časová složitost | ; Paměťová × časová složitost | ||
Verze z 2. 10. 2017, 09:08
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!
Má to ale jeden háček — musí nám stačit systémové prostředky pro daný algoritmus, zejména operační paměť. ;)
- 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í.
- Viz průměrná složitost.
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í:y = 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), kdeije lib. konstanta).
- roste jako libovolný polynom (omezen
-
O(2N)— exponenciální- Viz například: Hanoiské věže.
Úkol: Navrhněte algoritmus a odhadněte složitost
- Hledání maxima
Maximální a průměrná složitost
- Počet vykonaných operací se může lišit podle podoby konkrétních dat.
- Třeba při řazení podle abecedy může být počet operací jiný pro téměř setříděná data a jiná pro data, která jsou úplně přeházená.
- Některé algoritmy mohou mít velmi dobré chování ve většině případů, ale pro nešťastně uspořádaná data mohou mít složitost větší. (Viz třeba známý řadící algoritmus QuickSort.)
- Při cestě do školy vstanu tak, abych v průměrném případě dorazil včas. Pokud dojde k nehodě na silnici, může se stát, že se zpozdím. Ale je to málo pravděpodobné a vyrážet o hodinu dříve pro případ nehody by bylo nepraktické — řeším průměrnou délku cesty.
- Na druhou stranu pokud jdu k maturitě, čtvrthodinové zpoždění by znamenalo, že budu muset maturovat až na podzim a proto raději hodinu počkám — zajímá mě spíše délka cesty v nejhorším případě.
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.
- Paměťová × časová složitost
