Asymptotická složitost

časová složitost problému závislející lineárně na velikosti vstupů

Při řešení úloh pomocí výpočetní techniky musíme mít nástroj, kterým dokážeme porovnat efektivitu a rychlost vykonávání jednotlivých algoritmů. Pro tento účel byly zavedeny pojmy asymptotická složitost a operační náročnost algoritmu.

Grafické porovnání různých tříd složitosti s ohledem na změnu velikosti vstupních dat.

Asymptotická složitost je způsob klasifikace počítačových algoritmů. Určuje operační náročnost algoritmu tak, že zjišťuje, jakým způsobem se bude chování algoritmu měnit v závislosti na změně velikosti (počtu) vstupních dat. Zapisuje se pomocí Landauovy notace (též „Omikron notace“, nebo „velké O notace“) jako (např. ). Obvykle se používá asymptotická časová a prostorová složitost.

Používaný zápis znamená, že náročnost algoritmu je menší než , kde a jsou vhodně zvolené konstanty a je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, tzn. . Zajímá nás jen chování funkce pro velké hodnoty .

Například časová složitost (lineární) říká, že doba trvání práce algoritmu se zvýší přibližně tolikrát, kolikrát se zvýší velikost vstupu. Na druhou stranu u složitosti se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu dvakrát, potřebný čas se zvýší přibližně čtyřikrát. U časové složitosti naopak na délce vstupu vůbec nezáleží a potřebný čas nepřevýší nějakou pevnou mez. Podobně je tomu i u prostorové složitosti, jen s tou změnou, že se jedná o potřebné paměťové (prostorové) nároky v závislosti na délce vstupních dat.

Třídy složitosti editovat

Algoritmy můžeme podle hodnot   nějakého kritéria rozřadit do tříd. Kritéria jsou časová a paměťová složitost, dále pro paralelní a distribuované algoritmy komunikační složitost. Rozlišuje se složitost v nejhorším případě (která se odhaduje jednodušeji) a složitost v průměrném případě. Nejčastěji, tedy implicitně, se uvažuje o časové složitosti algoritmu v nejhorším případě.

Složitost problému je složitost nejlepšího algoritmu, který ho řeší. Každý konkrétní algoritmus poskytuje horní odhad složitosti.

Velikost dat   se obvykle měří v bitech, bytech anebo buňkách pevné velikosti (z hlediska asymptotické složitosti je rozdíl jen v multiplikativní konstantě), ale někdy se pro zjednodušení uvažuje jiné  . Například v grafových algoritmech se uvažuje graf o   vrcholech a takový graf může (a v některých případech musí) mít až   hran. Jiný příklad je čtvercová matice o straně  , která ve skutečnosti obsahuje až   položek.

V případě algoritmu rychlého řazení je časová složitost při obvyklé implementaci v nejhorším případě   a v průměrném případě  . Algoritmus násobení čtvercových matic velikosti   podle definice má kubickou složitost  , tj. problém násobení matic má složitost nejhůř kubickou. Strassenův algoritmus násobení matic má složitost přibližně   a jsou známy algoritmy s ještě lepší asymptotickou složitostí. Podobně diskrétní Fourierova transformace počítaná přímočaře podle definice má složitost   a algoritmus rychlé Fourierovy transformace má složitost  .

Časová složitost a třídy P a NP editovat

Pokud je časová složitost f(N) polynom, hovoříme o polynomiálně omezených algoritmech. Takové problémy, které řeší nějaký polynomiální algoritmus, patří do třídy složitosti P.

Pokud pro daný problém existuje polynomiálně omezený algoritmus, který ověří správnost řešení (dodaného někým jiným), hovoříme o nedeterministicky polynomiálním problému (polynomiálně omezený algoritmus, který řešení tohoto problému dokáže nalézt, zde obecně existovat nemusí). Tyto problémy tvoří třídu složitosti NP. Ekvivalentně lze tuto třídu definovat jako množinu problémů, které lze řešit na nedeterministickém Turingově stroji v polynomiálně omezeném čase. Do třídy NP patří například problém obchodního cestujícího, splnitelnost formule výrokové logiky a mnoho dalších, včetně všech problémů z třídy P.

Jednou z největších současných otevřených otázek teoretické informatiky je problém, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není (viz NP-úplnost a problém P versus NP).[zdroj?]

Složitost algoritmů a složitost problémů editovat

Je dobré rozlišovat dvě věci uvedené v nadpisu i v tomhle článku. Složitost algoritmu je odhad složitosti konkrétního algoritmu. Obvykle nás zajímá horní odhad, případně průměrný případ. Složitost problému je složitost nejlepšího algoritmu, který problém řeší. Zde je zajímavý dolní odhad, který se dokazuje pomocí teoretických nástrojů. Přitom každý konkrétní algoritmus poskytuje horní odhad složitosti problému.

Typické příklady časové složitosti editovat

Některé asymptotické složitosti (v proměnné   s konstantou  ) mají i své triviální pojmenování. V následující tabulce jsou seřazeny od nejmenší po největší.

Notace Název Příklad algoritmu
  konstantní Skok na prvek v poli dle indexu
  dvojitě logaritmická Interpolační vyhledávání
  logaritmická Binární vyhledávání
  polylogaritmická K-server problém
  odmocninová Vyhledávání v k-d stromu
  lineární Hledání prvku v neseřazeném poli
  linearitmická Řazení slučováním
  kvadratická Diskrétní Fourierova transformace, přímočaře podle definice
  kubická Násobení matic, přímočaře podle definice
  kvartická Nalezení podmatice s největším součtem pomocí dynamického programování, naivně
  polynomiální Karmarkův algoritmus
  exponenciální Problém obchodního cestujícího pomocí dynamického programování
  faktoriálová Problém obchodního cestujícího hrubou silou
  dvojitě exponenciální Ověření pravdivosti tvrzení zapsaného v Presburgově aritmetice

Existují i funkce, u nichž nelze složitost vůbec shora rozumně omezit. Příkladem budiž Ackermannova funkce.

Snižování výpočetní složitosti algoritmů editovat

Snahou programátorů, ale i teoretiků, je asymptotickou složitost dostat alespoň na polynomiální úroveň, horší složitosti jsou v reálných aplikacích (tedy u vyšších N) nepoužitelné. Typickým příkladem je diskrétní Fourierova transformace, která v obecném tvaru má asymptotickou složitost O(N2), proto je nevhodná pro transformaci vektorů větších délek. Existuje rychlá verze této transformace označovaná jako rychlá Fourierova transformace, která využívá skutečnosti, že pro délky vektorů N=KM (kde K je určeno radixem transformace 2,4,8,… a M je přirozené číslo), lze tento problém spočítat se složitostí O(N log N).

Pro opravdu velká data jsou často i nelineární algoritmy příliš náročné, vizte velká data. Když nemáme vhodný algoritmus, poskytující přesné výsledky, tak použijeme jiný algoritmus a pak se musíme spokojit s přibližným řešením, pravděpodobně správným řešením, heuristickým řešením, anebo vhodnými technikami zmenšit zpracovávaná data.

Běžné implementační až hackerské triky obvykle zrychlí konkrétní složitost algoritmu, tj. sníží multiplikativní konstantu v asymptotické složitosti, ale nezmění asymptotickou složitost. Sem patří inline funkce, rozvíjení těla cyklu a převedení rekurze na iteraci. Na druhé straně, když takové optimalizace vynecháme, ignorujeme, nebo nemáme ve svém kompilátoru, tak to asymptotickou složitost nezhorší. Pomůže tak použití výkonnějšího hardwaru.

Amortizovaná časová složitost editovat

Na tuto kapitolu je přesměrováno heslo Amortizovaná složitost.

Amortizovaná časová složitost je průměrný čas potřebný pro vykonání určité operace v sekvenci operací v nejhorším případě. Na rozdíl od časové složitosti v průměrném případě nevyužívá pravděpodobnosti a předpokladů o rozložení dat. U amortizované složitosti je průměrný čas na operaci skutečně zaručený.

Tato metoda vyžaduje znalost toho, které sekvence operací jsou vůbec možné. Nejčastěji se to týká analýzy datových struktur, které si mezi jednotlivými operacemi udržují určitý stav. Některé datové struktury mají totiž takovou vnitřní organizaci, že na ní závisí složitost, a organizovanost dat se může během posloupnosti operací měnit. Základní myšlenka amortizované analýzy tkví v tom, že operace s velkou složitostí změní stav struktury tak, že tento nejhorší případ nemůže nastat po dlouhý čas, tudíž amortizuje svou cenu.

Amortizovaná složitost se používá v případě, kdy některá konkrétní operace (typicky na datové struktuře) má v nejhorším případě velkou složitost, ale na vykonání této operace si dokážeme našetřit z předchozích operací v (libovolné) posloupnosti.

Jako jednoduchý příklad můžeme uvést specifickou implementaci dynamického pole, která zdvojnásobuje velikost pole pokaždé, když dojde k jeho naplnění. V tomto případě je tedy nutná realokace, v nejhorším případě tato operace potřebuje čas až O(N). Samotné vkládání prvků (bez nutnosti realokace) vyžaduje čas O(1), pro N prvků tedy také O(N). Pro vložení N prvků (včetně realokace) je tedy potřeba O(N) + O(N) = O(N), amortizovaný čas na jedno vložení prvku je pak O(N)/N = O(1).

Příklad výpočetní náročnosti editovat

Jedna operace zde trvá jednu nanosekundu.

Asymptotická složitost Velikost vstupních dat
10 20 50 100 1 000 1 000 000 1 000 000 000 1020
  2 ns 3 ns 3 ns 3 ns 4 ns 5 ns 5 ns 7 ns
  4 ns 5 ns 6 ns 7 ns 10 ns 20 ns 30 ns 67 ns
  4 ns 8 ns 8 ns 10 ns 32 ns 1 μs 32 μs 10 s
  10 ns 20 ns 50 ns 100 ns 1 μs 1 ms 1 s 3 171 let
  34 ns 87 ns 283 ns 665 ns 10 μs 20 ms 30 s 210 675 let
  100 ns 400 ns 3 μs 10 μs 1 ms 16 min 40 s 32 let
  1 μs 8 μs 125 μs 1 ms 1 s 32 let
  10 μs 160 μs 6 ms 100 ms 16 min 40 s 31 688 088 let
  1 μs 1 ms 13 dní 40×1012 let
  59 μs 4 s 22 760 000 let
  4 ms 77 let
  10 s 3,32×109 let
  5,7×10291 let

Nebezpečí používání asymptotické složitosti editovat

Multiplikativní konstanta nějakého algoritmu může být příliš velká (např.  ) a tedy algoritmus prakticky nepoužitelný. Takovéto algoritmy se nazývají galaktické. Typickým příkladem jsou algoritmy pro násobení matic, kde se pro praktické použití hodí Strassenův algoritmus, ačkoli jsou známy algoritmy s asymptoticky lepší složitostí.

Podobný případ je, když asymptoticky lepší algoritmus A má větší multiplikativní konstantu než alg. A*, ale v důsledku toho je pro reálně používané, tj. dostatečně malé, velikosti dat výhodnější A*, protože A* má menší režii.

Odkazy editovat

Související články editovat

Externí odkazy editovat