Složitost algoritmu
Z MiS
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
