Složitost algoritmu

Z MiS
(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
m (Přidán odkaz na Algoritmus)
(→Asymptotická složitost: Doplněny příklady algoritmů dané složitosti.)
 
(Nejsou zobrazeny 3 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 &rarr; lepší algoritmus!</div>
 
<div class="Poznamka">Rychlejší algoritmus &rarr; lepší algoritmus!</div>
 +
<div class="Varovani">Má to ale jeden háček &mdash; musí nám stačit systémové prostředky pro daný algoritmus, zejména operační paměť. ;)</div>
  
 
;Problém &mdash; čas je ovlivněn:
 
;Problém &mdash; čas je ovlivněn:
Řádka 15: Řádka 16:
 
* ...
 
* ...
  
−
; Zjednodušení:
+
 
−
*Neměříme čas, ale počet operací (tím omezíme vliv HW).
+
== Měření složitosti ==
−
*Nepočítáme všechny instrukce
+
# ''Neměříme čas, ale počet operací!''
−
**obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk.
+
#* Tím omezíme vliv konkrétního HW.
−
**Tím eliminujeme vliv použitého překladače, knihoven, jazyka,...
+
# ''Nepočítáme všechny dílčí operace!''
−
*Zajímají nás velká data, řádový růst (viz asymptotická složitost).
+
#* 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. (Eliminujeme vliv zadání.)
+
#* 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í.
 +
#* 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) &mdash; lineární
+
* <code>O(N)</code> &mdash; 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&nbsp;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>) &mdash; kvadratický
+
* <code>O(N<sup>2</sup>)</code> &mdash; kvadratický ... například řazení opakovaným hledáním maxima
−
*O(N<sup>3</sup>) &mdash; kubický
+
* <code>O(N<sup>3</sup>)</code> &mdash; 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>) &mdash; exponenciální
+
* <code>O(2<sup>N</sup>)</code> &mdash; 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].
  
−
; Úkol &mdash; Navrhněte algoritmus a odhadněte složitost
+
<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&nbsp;telefonním seznamu:
 +
* Běžné hledání v&nbsp;telefonním seznamu má složitost <code>O(N.log(N))</code>.
 +
* Složitost <code>O(N)</code> &mdash; lineární, tedy stále dobrou &mdash; by mělo hledání v&nbsp;telefonním seznamu podle telefonního čísla. Museli byste projít všechny položky a&nbsp;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&nbsp;telefonního seznamu museli zavolat, on by vám řekl telefonní číslo svého nejlepšího kamaráda a&nbsp;vaším úkolem by bylo nalézt v&nbsp;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&nbsp;seznamu zavolejte, tam vám řeknou telefonní číslo kamaráda, najděte jeho jméno, zavolejte mu, oslovte ho jménem a&nbsp;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&nbsp;nehodě na silnici, může se stát, že se zpozdím. Ale je to málo pravděpodobné a vyrážet o&nbsp;hodinu dříve pro případ nehody by bylo nepraktické &mdash; řeším ''průměrnou'' délku cesty.
 +
* Na druhou stranu pokud jdu k&nbsp;maturitě, čtvrthodinové zpoždění by znamenalo, že budu muset maturovat až na podzim a&nbsp;proto raději hodinu počkám &mdash; zajímá mě spíše délka cesty ''v&nbsp;nejhorším případě''.
 +
</div>
 +
  
 
== Související pojmy ==
 
== Související pojmy ==
Řádka 50: Řá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.
−
 
−
; 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
 
; 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ů.

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


Měření složitosti

  1. Neměříme čas, ale počet operací!
    • Tím omezíme vliv konkrétního HW.
  2. 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,...
  3. Zajímají nás velká data, řádový růst!
  4. Zajímá nás maximální nebo průměrná složitost!


Asymptotická složitost

Příklady růstu počtu operací

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 čas O(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

  • 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
Paměťová × časová složitost

Viz také

Zdroje

Citováno z „http://mis.e-mis.cz/index.php/Slo%C5%BEitost_algoritmu“
Osobní nástroje
Jmenné prostory
Varianty
Akce
Výuka
Navigace
Nástroje