Složitost algoritmu

Z MiS
(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
m (Přidáno upozornění na omezení kapacity paměti.)
(Asymptotická složitost: Doplněny příklady algoritmů dané složitosti.)
 
Řádka 39: Řádka 39:
  
 
;Příklady růstu počtu operací
 
;Příklady růstu počtu operací
* <code>O(N)</code> &mdash; lineární
+
* <code>O(N)</code> &mdash; 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&nbsp;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> &mdash; kvadratický
+
* <code>O(N<sup>2</sup>)</code> &mdash; kvadratický ... například řazení opakovaným hledáním maxima
 
* <code>O(N<sup>3</sup>)</code> &mdash; kubický
 
* <code>O(N<sup>3</sup>)</code> &mdash; kubický
 
*Polynomiální
 
*Polynomiální
Řádka 50: Řádka 50:
 
* <code>O(2<sup>N</sup>)</code> &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].
 +
 +
<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
 
<div class="Priklad">Úkol: Navrhněte algoritmus a odhadněte složitost
 
* Hledání maxima
 
* Hledání maxima
 
</div>
 
</div>
 
  
 
== Maximální a průměrná složitost ==
 
== Maximální a průměrná 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

Osobní nástroje
Jmenné prostory
Varianty
Akce
Výuka
Navigace
Nástroje