Složitost algoritmu
Z MiS
(Rozdíly mezi verzemi)
m (Přidáno upozornění na omezení kapacity paměti.) |
(Přidány třídy P a NP.) |
||
| (Nejsou zobrazeny 2 mezilehlé verze od 1 uživatele.) | |||
| Řádka 17: | Řádka 17: | ||
| − | == Měření složitosti == | + | == Měření složitosti – používaná zjednodušení == |
# ''Neměříme čas, ale počet operací!'' | # ''Neměříme čas, ale počet operací!'' | ||
#* Tím omezíme vliv konkrétního HW. | #* Tím omezíme vliv konkrétního HW. | ||
| Řádka 23: | Řádka 23: | ||
#* Obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk). | #* 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,... | #* Tím eliminujeme vliv použitého překladače, knihoven, jazyka, procesorové architektury,... | ||
| + | # ''Zajímá nás průměrná složitost nebo složitost v nejhorším případě!'' | ||
| + | #* Tím eliminujeme vliv konkrétního zadání. | ||
| + | #* Viz [[#Složitost v průměrném nebo nejhorším případě|průměrná složitost]]. | ||
# ''Zajímají nás velká data, řádový růst!'' | # ''Zajímají nás velká data, řádový růst!'' | ||
#* Viz [[#Asymptotická složitost|asymptotická složitost]]. | #* Viz [[#Asymptotická složitost|asymptotická složitost]]. | ||
#* Malé instance skončí v rozumném čase, i když se budou počítat neefektivně. | #* Malé instance skončí v rozumném čase, i když se budou počítat neefektivně. | ||
| − | # '' | + | # ''Stačí nám horní mez růstu počtu operací'' |
| − | #* | + | #* Místo snahy o přesné vyčíslení počtu operací nám stačí, že počet operací neporoste rychleji než některá matematická funkce. |
| − | #* Viz [[# | + | #* Například pro N prvků vstupních dat nebude nikdy počet operací vyšší než <code>y = A.N</code>, kde <code>A</code> je zvolená konstanta. |
| + | #* Viz [[#Asymptotická složitost|asymptotická složitost]]. | ||
== Asymptotická složitost == | == Asymptotická složitost == | ||
| − | * | + | * Zkoumáme, jak se počet operací mění při zvětšování objemu vstupních dat. |
*Zapisujeme <code>O(f(N))</code> | *Zapisujeme <code>O(f(N))</code> | ||
** <code>N</code>... velikost dat | ** <code>N</code>... velikost dat | ||
| Řádka 39: | Řádka 43: | ||
;Příklady růstu počtu operací | ;Příklady růstu počtu operací | ||
| − | * <code>O(N)</code> — lineární | + | * <code>O(N)</code> — lineární ... např. hledání maxima posloupnosti |
*Lepší než lineární | *Lepší než lineární | ||
| − | ** <code>O(log(N))</code> | + | ** <code>O(log(N))</code> ... např. hledání prvku v seřazeném seznamu |
** <code>O(sqrt(N))</code> | ** <code>O(sqrt(N))</code> | ||
| − | * <code>O(N.log(N))</code> | + | * <code>O(N.log(N))</code> ... př.: rychlé algoritmy pro řazení |
| − | * <code>O(N<sup>2</sup>)</code> — kvadratický | + | * <code>O(N<sup>2</sup>)</code> — kvadratický ... například řazení opakovaným hledáním maxima |
* <code>O(N<sup>3</sup>)</code> — kubický | * <code>O(N<sup>3</sup>)</code> — kubický | ||
*Polynomiální | *Polynomiální | ||
| Řádka 50: | Řádka 54: | ||
* <code>O(2<sup>N</sup>)</code> — 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 | <div class="Priklad">Úkol: Navrhněte algoritmus a odhadněte složitost | ||
| Řádka 55: | Řádka 67: | ||
</div> | </div> | ||
| − | + | == Složitost v průměrném či nejhorším případě == | |
| − | == | + | |
* Počet vykonaných operací se může lišit podle podoby konkrétních dat. | * 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á. | * 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á. | ||
| Řádka 65: | Řádka 76: | ||
* 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ě''. | * 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> | </div> | ||
| + | |||
| + | == Třídy P a NP == | ||
| + | ; Třída P (polynomiální algoritmy) | ||
| + | * Zahrnuje všechny algoritmy, jejichž složitost lze omezit polynomem. | ||
| + | * Tedy všechny algoritmy se složitostí nejvýše <code>O(N<sup>K</sup>)</code>, kde <code>K</code> je libovolná konstanta. | ||
| + | ; Třída NP (nedeterministicky polynomiální algoritmy) | ||
| + | * Zahrnuje všechny algoritmy, u kterých pokud známe řešení, můžeme jeho správnost ověřit v polynomiálním čase. | ||
| + | * Nemusíme umět řešení '''najít''', stačí umět ověřit správnost řešení, které nám někdo dá. | ||
| + | * Řešení pak obvykle hledáme pomocí nějaké heuristiky – zjednodušeného posutpu, jehož výsledek nemusí být vždy správný, ale který běží v polynomiálním čase. Správnost řešení pak ověřujeme a pokud není správné, hledáme znovu stejnou heuristikou s upravenými parametry. | ||
| + | |||
Aktuální verze z 7. 10. 2026, 04:26
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 – používaná zjednodušení
- 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ímá nás průměrná složitost nebo složitost v nejhorším případě!
- Tím eliminujeme vliv konkrétního zadání.
- Viz průměrná složitost.
- 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ě.
- Stačí nám horní mez růstu počtu operací
- Místo snahy o přesné vyčíslení počtu operací nám stačí, že počet operací neporoste rychleji než některá matematická funkce.
- Například pro N prvků vstupních dat nebude nikdy počet operací vyšší než
y = A.N, kdeAje zvolená konstanta. - Viz asymptotická složitost.
Asymptotická složitost
- Zkoumáme, jak se počet operací mění při zvětšová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
Složitost v průměrném či nejhorším případě
- 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ě.
Třídy P a NP
- Třída P (polynomiální algoritmy)
- Zahrnuje všechny algoritmy, jejichž složitost lze omezit polynomem.
- Tedy všechny algoritmy se složitostí nejvýše
O(NK), kdeKje libovolná konstanta.
- Třída NP (nedeterministicky polynomiální algoritmy)
- Zahrnuje všechny algoritmy, u kterých pokud známe řešení, můžeme jeho správnost ověřit v polynomiálním čase.
- Nemusíme umět řešení najít, stačí umět ověřit správnost řešení, které nám někdo dá.
- Řešení pak obvykle hledáme pomocí nějaké heuristiky – zjednodušeného posutpu, jehož výsledek nemusí být vždy správný, ale který běží v polynomiálním čase. Správnost řešení pak ověřujeme a pokud není správné, hledáme znovu stejnou heuristikou s upravenými parametry.
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
