Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:hodnoceni_slozitosti_algoritmu

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

pitel:isz:hodnoceni_slozitosti_algoritmu [03. 07. 2012, 13.53:45] (aktuální)
Řádek 1: Řádek 1:
 +====== 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í
 +<​note>​ 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).</​note>​
 +
 +==== Složitost O ====
 +[[wp>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 Θ((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ý.
 +  - Θ(//​k<​sup>​n</​sup>//​),​ 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
/var/www/wiki/data/pages/pitel/isz/hodnoceni_slozitosti_algoritmu.txt · Poslední úprava: 03. 07. 2012, 13.53:45 (upraveno mimo DokuWiki)