Hodnocení složitosti algoritmů

http://xoax.net/comp/sci/algorithms/Lesson6.php

Pro hodnocení kvality algoritmu i pro porovnání dvou různých algoritmů jsou zapotřebí vhodná kriteria. Účelnými parametry jsou čas potřebný pro provedení algoritmu a paměťový prostor, který zaujímá program a jeho data. Čas i prostor potřebný pro algoritmus závisí na velikosti zpracovávaných dat. Proto má složitost nejčastěji podobu funkce velikosti zpracovávaných dat, udávané počtem položek N.

Asymptotická složitost

Jedná se o nejčastější hodnotící kritérium algoritmů. Vyjadřuje se porovnáním algoritmu s určitou funkcí pro N blížící se nekonečnu. Porovnávání má podobu tří různých složitostí.

O – Omikron (velké O, O, big O) – horní hranice chování

Ω – Omega – dolní hranice chování

Θ – Theta – vyjadřuje třídu chování

Skutečnost, že asymptotická složitost jednoho algoritmu je menší než jiného nemusí znamenat, že pro každé n je první algoritmus rychlejší. Složitost algoritmu vyjadřuje obecné chování třídy algoritmů, čas algoritmu vyjadřuje konkrétní dobu pro jisté N. Pro praktické aplikace se nejčastěji algoritmy charakterizují složitostí O, která vyjadřuje „nejhorší případ“ (worst case).

Složitost O

Big O notation

Taková složitost vyjadřuje horní hranici časového chování algoritmu. O(g(n)) označuje množinu funkcí f(n), pro které platí:

{f(n) : ∃(c>0, n0>0) takové, že ∀(n>=n0) platí [0<=f(n)<=c*g(n)]}

kde c a n0 jsou jisté vhodné kladné konstanty. Pak zápis f(n)=O(g(n)), označuje, že funkce f(n) roste maximálně tak rychle jako funkce g(n). Funkce g(n) je horní hranicí množiny takových funkcí, určené zápisem O(g(n)).

Složitost Ω

Složitost Ω vyjadřuje dolní hranici časového chování algoritmu. Ω(g(n)) označuje množinu všech funkcí f(n) pro které platí:

{f(n) : ∃(c>0, n0>0) takové, že ∀n>=n0 platí [0<=c*g(n)<=f(n)]}

kde c a n0 jsou určité vhodné kladné konstanty. Pak zápis f(n)=(Ω(g(n))) označuje, že funkce f(n) roste minimálně tak rychle, jako funkce g(n). Funkce g(n) je dolní hranicí množiny všech funkcí, určených zápisem (Ω(g(n))).

Složitost Θ

Složitost Θ1) Théta vyjadřuje třídu časového chování algoritmu. Θ(g(n)) označuje množinu všech funkcí f(n), pro něž platí:

{f(n) : ∃(c1>0, c2>0, n0>0) takové, že ∀(n>=n0) platí [0<=c1*g(n)<=f(n)<=c2*g(n)]}

kde c1, c2 and n0 jsou vhodné kladné konstanty. Složitost vyjádřená zápisem Theta (Θ) označuje časové chování shodné jako daná funkce. Pak zápis f(n)= Θ(g(n)) označuje, že funkce f(n) roste tak rychle jako funkce g(n). Funkce g(n) vyjadřuje horní a současně dolní hranici množiny funkcí, označených zápisem Θ(g(n)).

Klasifikace algoritmů

Θ(1) je označení algoritmů s konstantní časovou složitostí. Např. indexování prvků v poli.

Θ(log(n)) je označení algoritmů s logaritmickou časovou složitostí. Základ logaritmu není podstatný, protože hodnoty logaritmu pro různé základy se liší pouze konstantou vzájemného převodu. Logaritmickou složitostí se vyznačují např. rychlé vyhledávací algoritmy (půlení intervalů v seřazeném seznamu).

Θ(n) je označení algoritmů s lineární časovou složitostí. Tuto složitost mají běžné vyhledávací algoritmy (hlednání v neseřazeném poli) a řada algoritmů sekvenčně zpracovávajících datové struktury.

Θ(n*log(n)) je označení algoritmů nazývané také linearitmické. Tuto časovou složitost mají např. rychlé řadicí algoritmy (quicksort).

Θ(n²) je označení algoritmů s kvadratickou časovou složitostí. Takovou časovou složitostí se vyznačují algoritmy sestavené z dvojnásobného počítaného cyklu do n. Patří mezi ně řada klasických řadicích algoritmů (bubblesort).

Θ(n³) je označení algoritmů s kubickou časovou složitostí. Algoritmy s touto časovou složitostí jsou prakticky použitelné především pro málo rozsáhlé problémy. Kdykoli se n zdvojnásobí, čas zpracování je osminásobný.

Θ(kn), kde k je reálné kladné číslo, je označení algoritmů s exponenciální (pro k=2 binomickou) časovou složitostí. Existuje několik prakticky použitelných algoritmů s touto složitostí. Velmi často se označují jako algoritmy pracující s “hrubou silou” (brute-force algorithms). Když u binomické časové složitosti n vzroste o 1, čas se zdvojnásobí.

Určování časové složitosti

Při určování časové složitosti je třeba vyjít ze složitostí popsaných v klasifikaci algoritmů výše. Dále musíme vzít v úvahu, zda je daný algoritmus řešitelný. Příklad neřešitelného algoritmu – algoritmus, který by rozhodnul, zda nějaký algoritmus skončí po určitém počtu kroků nebo ne.

Shrnutí

casová a paměťová náročnost

asymptotická složitost: omikron (vrchní), omega (spodní), theta (třída chování)

třídy: konstantní, lineární, logaritmická, linearirmická, kvadratická, kubická, exponenciální

řešitelnost algoritmu, přířazení do třídy, matematicky: turingův stroj, nebo prostě studiem algoritmu