Složitost algoritmu
Z MiS
(Rozdíly mezi verzemi)
(→Složitost jako míra pro srovnání algoritmů: Měření složitosti jako samostatná kapitola.) |
(→Asymptotická složitost: Doplněny příklady algoritmů dané složitosti.) |
||
| (Nejsou zobrazeny 2 mezilehlé verze od 1 uživatele.) | |||
| Řá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 == | ||
*Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat. | *Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat. | ||
*Zapisujeme <code>O(f(N))</code> | *Zapisujeme <code>O(f(N))</code> | ||
| − | **N... velikost dat | + | ** <code>N</code>... velikost dat |
| − | **f(N)... funkce, jejímž růstem lze limitovat růst počtu operací | + | ** <code>f(N)</code>... funkce, jejímž růstem lze limitovat růst počtu operací |
| − | **Pokud je velikost vstupu N, pak je složitost limitována funkcí <code>A+B.f(N)</code> | + | **Pokud je velikost vstupu <code>N</code>, pak je složitost limitována funkcí: <code>y = A+B.f(N)</code> |
;Příklady růstu počtu operací | ;Příklady růstu počtu operací | ||
| − | *O(N) — lineární | + | * <code>O(N)</code> — lineární ... např. hledání maxima posloupnosti |
*Lepší než lineární | *Lepší než lineární | ||
| − | **O(log(N)) | + | ** <code>O(log(N))</code> ... např. hledání prvku v seřazeném seznamu |
| − | **O(sqrt(N)) | + | ** <code>O(sqrt(N))</code> |
| − | *O(N.log(N)) | + | * <code>O(N.log(N))</code> ... př.: rychlé algoritmy pro řazení |
| − | *O(N<sup>2</sup>) — kvadratický | + | * <code>O(N<sup>2</sup>)</code> — kvadratický ... například řazení opakovaným hledáním maxima |
| − | *O(N<sup>3</sup>) — kubický | + | * <code>O(N<sup>3</sup>)</code> — kubický |
*Polynomiální | *Polynomiální | ||
| − | **roste jako libovolný polynom (omezen O(N<sup>i</sup>), kde i je lib. konstanta). | + | **roste jako libovolný polynom (omezen <code>O(N<sup>i</sup>)</code>, kde <code>i</code> je lib. konstanta). |
| − | *O(2<sup>N</sup>) — exponenciální | + | * <code>O(2<sup>N</sup>)</code> — exponenciální |
** Viz například: [http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe Hanoiské věže]. | ** Viz například: [http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe Hanoiské věže]. | ||
| − | ; | + | <div class="Priklad"> |
| + | Abyste si lépe uvědomili, jaký vliv má růst složitosti algoritmu, můžete si to zkusit představit na hledání v telefonním seznamu: | ||
| + | * Běžné hledání v telefonním seznamu má složitost <code>O(N.log(N))</code>. | ||
| + | * Složitost <code>O(N)</code> — lineární, tedy stále dobrou — by mělo hledání v telefonním seznamu podle telefonního čísla. Museli byste projít všechny položky a hledat člověka, který má zadané telefonní číslo. | ||
| + | * Kvadratickou složitost <code>O(N<sup>2</sup>)</code> by měla úloha, kdy byste každému člověku z telefonního seznamu museli zavolat, on by vám řekl telefonní číslo svého nejlepšího kamaráda a vaším úkolem by bylo nalézt v seznamu jméno toho kamaráda (opět hledáním položku po položce). (Tady už by se vyplatilo si telefonní seznam nejprve seřadit podle telefonních čísel. To by sice zabralo čas <code>O(N.log(N))</code>, ale pak už byste hledali se složitostí <code>O(log(N))</code>.) | ||
| + | * Kubická složitost: na každé číslo v seznamu zavolejte, tam vám řeknou telefonní číslo kamaráda, najděte jeho jméno, zavolejte mu, oslovte ho jménem a on vám řekne číslo svého kamaráda. Jeho jméno najděte. ;) | ||
| + | </div> | ||
| + | |||
| + | <div class="Priklad">Úkol: Navrhněte algoritmus a odhadněte složitost | ||
* Hledání maxima | * Hledání maxima | ||
| + | </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 55: | Řádka 78: | ||
*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 | ||
Aktuální verze z 18. 10. 2021, 13:21
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í ... např. hledání maxima posloupnosti - Lepší než lineární
-
O(log(N))... např. hledání prvku v seřazeném seznamu -
O(sqrt(N))
-
-
O(N.log(N))... př.: rychlé algoritmy pro řazení -
O(N2)— kvadratický ... například řazení opakovaným hledáním maxima -
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.
Abyste si lépe uvědomili, jaký vliv má růst složitosti algoritmu, můžete si to zkusit představit na hledání v telefonním seznamu:
- Běžné hledání v telefonním seznamu má složitost
O(N.log(N)). - Složitost
O(N)— lineární, tedy stále dobrou — by mělo hledání v telefonním seznamu podle telefonního čísla. Museli byste projít všechny položky a hledat člověka, který má zadané telefonní číslo. - Kvadratickou složitost
O(N2)by měla úloha, kdy byste každému člověku z telefonního seznamu museli zavolat, on by vám řekl telefonní číslo svého nejlepšího kamaráda a vaším úkolem by bylo nalézt v seznamu jméno toho kamaráda (opět hledáním položku po položce). (Tady už by se vyplatilo si telefonní seznam nejprve seřadit podle telefonních čísel. To by sice zabralo časO(N.log(N)), ale pak už byste hledali se složitostíO(log(N)).) - Kubická složitost: na každé číslo v seznamu zavolejte, tam vám řeknou telefonní číslo kamaráda, najděte jeho jméno, zavolejte mu, oslovte ho jménem a on vám řekne číslo svého kamaráda. Jeho jméno najděte. ;)
Ú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
