Výpočetní složitost

Výpočetní složitost je pojem v informatice a teorii algoritmů , který označuje funkci závislosti množství práce, kterou nějaký algoritmus vykoná, na velikosti vstupních dat. Obor, který studuje výpočetní složitost, se nazývá teorie výpočetní složitosti . Množství práce se obvykle měří v podmínkách abstraktních pojmů času a prostoru nazývaných výpočetní zdroje . Čas je určen počtem elementárních kroků potřebných k vyřešení problému, zatímco prostor je určen množstvím paměti nebo místa na paměťovém médiu.. V této oblasti je tedy učiněn pokus odpovědět na ústřední otázku vývoje algoritmu: „jak se změní doba provádění a množství obsazené paměti v závislosti na velikosti vstupu?“. Velikost vstupu je zde délka popisu problémových dat v bitech (například v problému cestujícího prodejce je délka vstupu téměř úměrná počtu měst a silnic mezi nimi) a velikost výstupu je délka popisu řešení problému (nejlepší trasa v problému cestujícího obchodníka).

Zejména teorie výpočetní složitosti definuje NP-úplné problémy , které nedeterministický Turingův stroj může vyřešit v polynomiálním čase , zatímco pro deterministický Turingův stroj není znám žádný polynomiální algoritmus . Obvykle se jedná o složité optimalizační problémy , například problém obchodního cestujícího .

S teoretickou informatikou úzce souvisí oblasti jako analýza algoritmů a teorie vyčíslitelnosti . Pojítkem mezi teoretickou informatikou a algoritmickou analýzou je skutečnost, že jejich tvorba je věnována analýze potřebného množství zdrojů určitých algoritmů pro řešení problémů, přičemž obecnější otázkou je možnost použití algoritmů pro takové problémy. Abychom byli konkrétní, pokusíme se klasifikovat problémy, které mohou nebo nemusí být vyřešeny s omezenými zdroji. Silné omezení dostupných zdrojů odlišuje teorii výpočetní složitosti od teorie výpočetní, která odpovídá na otázku, jaké problémy lze v zásadě řešit algoritmicky.

Časová a prostorová složitost

Teorie výpočetní složitosti vznikla z potřeby porovnat rychlost algoritmů, jasně popsat jejich chování (dobu provedení a velikost potřebné paměti) v závislosti na velikosti vstupu.

Počet elementárních operací vynaložených algoritmem k vyřešení konkrétní instance problému závisí nejen na velikosti vstupních dat, ale také na datech samotných. Například počet operací algoritmu řazení vložení je mnohem menší, pokud jsou vstupní data již setříděna. Abyste se vyhnuli takovým potížím, zvažte koncept časové složitosti algoritmu v nejhorším případě .

Časová složitost algoritmu (v nejhorším případě) je funkcí velikosti vstupních dat, která se rovná maximálnímu počtu elementárních operací, které algoritmus provede k vyřešení instance problému zadané velikosti.

Podobně jako u pojmu časové složitosti v nejhorším případě je definován pojem časové složitosti algoritmu v nejlepším případě . Zvažují také koncept průměrné doby běhu algoritmu , tedy matematické očekávání doby běhu algoritmu. Někdy se jednoduše říká: „ Časová složitost algoritmu “ nebo „ Doba běhu algoritmu “, což odkazuje na časovou složitost algoritmu v nejhorším, nejlepším nebo průměrném případě (v závislosti na kontextu).

Analogicky s časovou složitostí určují prostorovou složitost algoritmu , pouze zde nemluví o počtu elementárních operací, ale o množství použité paměti.

Asymptotická složitost

Navzdory tomu, že funkci časové složitosti algoritmu lze v některých případech přesně určit, ve většině případů nemá smysl hledat její přesnou hodnotu. Faktem je, že za prvé, přesná hodnota časové složitosti závisí na definici elementárních operací (složitost lze například měřit počtem aritmetických operací, bitových operací nebo operací na Turingově stroji ), a zadruhé jako velikost vstupních dat roste, příspěvek faktorů konstant a členů nižšího řádu objevujících se ve výrazu pro přesnou provozní dobu se stává extrémně nevýznamným.

Uvažování velkých vstupních dat a odhad řádu růstu doby běhu algoritmu vede ke konceptu asymptotické složitosti algoritmu. Algoritmus s menší asymptotickou složitostí je zároveň efektivnější pro všechna vstupní data, možná s výjimkou dat malé velikosti. Asymptotická notace se používá k zápisu asymptotické složitosti algoritmů :

Označení	Intuitivní vysvětlení	Definice
$f(n)\in O(g(n))$	$F$ je shora omezena funkcí (až do konstantního činitele) asymptoticky $G$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ nebo $\exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\in \Omega (g(n))$	$F$ je zdola omezena funkcí (až do konstantního faktoru) asymptoticky $G$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\in \Theta (g(n))$	$F$ ohraničený zdola i shora funkcí asymptoticky $G$	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|\leq \|C' g(n)\|$
$f(n)\in o(g(n))$	$G$ dominuje asymptoticky $F$	$\forall (C>0),\existuje n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\in \omega (g(n))$	$F$ dominuje asymptoticky $G$	$\forall (C>0),\existuje n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
$f(n)\sim g(n)$	$F$ je ekvivalentní asymptoticky $G$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Příklady

„vysávání koberce“ trvá čas lineárně závislý na jeho ploše ( ), to znamená, že koberec s dvojnásobnou plochou bude trvat dvakrát déle. V souladu s tím, se zvýšením plochy koberce o sto tisíckrát, objem práce se přísně proporcionálně zvyšuje o sto tisíckrát atd. $\Theta (A)$
"Najít jméno v telefonním seznamu" zabere pouze čas, logaritmicky závislé na počtu záznamů ( ), protože otevřením knihy přibližně uprostřed zmenšíme velikost "zbývajícího problému" na polovinu (tříděním jmen abecedně). V knize o objemu 1000 stran se tedy žádné jméno nenachází více než najednou (otevření knihy). Při zvýšení objemu stránek na sto tisíc se problém stále řeší v návštěvách. (Viz binární vyhledávání .) $O(\log _{2}(n))$ $\log _{2}1000\cca 10$ $\log _{2}100 000\cca 17$

Poznámky

Protože v asymptotickém odhadu složitosti je „logaritmus“ často zapsán bez uvedení základu - například . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

Je třeba zdůraznit, že tempo růstu doby provádění v nejhorším případě není jediným ani nejdůležitějším kritériem pro hodnocení algoritmů a programů. Zde je několik úvah, které vám umožní podívat se na kritérium běhu z jiných úhlů pohledu:

Pokud bude vytvářený program použit pouze několikrát, pak náklady na psaní a ladění programu budou převažovat nad celkovými náklady na program, tj. skutečná doba provádění nebude mít významný dopad na celkové náklady. V tomto případě by měl být preferován algoritmus, který je nejjednodušší implementovat.

Pokud bude program pracovat pouze s "malými" vstupními daty, pak bude rychlost růstu doby běhu méně důležitá než konstanta přítomná ve vzorci doby běhu [1] . Koncept „malosti“ vstupních dat přitom závisí také na přesné době provádění konkurenčních algoritmů. Existují algoritmy, jako je algoritmus celočíselného násobení , které jsou asymptoticky nejúčinnější, ale které se v praxi nikdy nepoužívají, a to ani pro velké problémy, protože jejich konstanty proporcionality jsou mnohem lepší než u jiných, jednodušších a méně "efektivních" algoritmy. Dalším příkladem jsou Fibonacciho haldy , navzdory jejich asymptotické účinnosti, z praktického hlediska je softwarová složitost implementace a velké hodnoty konstant ve vzorcích doby běhu činí méně atraktivními než běžné binární stromy [1] .

Pokud řešení nějaké úlohy pro n-vrcholový graf jedním algoritmem zabere čas (počet kroků) řádu n C a dalším - řádově n+n!/C, kde C je konstantní číslo , pak podle "polynomiální ideologie" je první algoritmus prakticky účinný a druhý ne, i když např. u C=10 (10 10 ) je situace právě opačná [2] .A. A. Zykov

Existují případy, kdy efektivní algoritmy vyžadují tak velké množství paměti stroje (bez možnosti použití externích paměťových médií), že tento faktor anuluje výhodu „efektivity“ algoritmu. Často je tedy důležitá nejen „časová složitost“, ale také „paměťová složitost“ (prostorová složitost).

V numerických algoritmech je přesnost a stabilita algoritmů neméně důležitá než jejich časová efektivita.

Třídy obtížnosti

Třída složitosti je soubor problémů rozpoznávání, pro které existují algoritmy, které jsou podobné výpočetní složitosti. Dva významní představitelé:

Třída P

Třída P obsahuje všechny ty úlohy, jejichž řešení je považováno za „rychlé“, to znamená, že doba řešení závisí polynomiálně na velikosti vstupu. To zahrnuje třídění , vyhledávání v poli, zjišťování konektivity grafů a mnoho dalších.

Třída NP

Třída NP obsahuje problémy, které nedeterministický Turingův stroj dokáže vyřešit v polynomickém počtu kroků od velikosti vstupu. Jejich řešení lze zkontrolovat deterministickým Turingovým strojem v polynomickém počtu kroků. Je třeba poznamenat, že nedeterministický Turingův stroj je pouze abstraktní model, zatímco moderní počítače odpovídají deterministickému Turingovu stroji s omezenou pamětí. Protože deterministický Turingův stroj lze považovat za speciální případ nedeterministického Turingova stroje , zahrnuje třída NP třídu P a také některé problémy, pro něž existují pouze algoritmy, které exponenciálně závisí na velikosti vstupu (tj. jsou neefektivní pro velké vstupy) je známo řešit. Třída NP zahrnuje mnoho slavných problémů, jako je problém cestujícího prodejce , problém splnitelnosti pro booleovské vzorce , faktorizace atd.

Problém rovnosti tříd P a NP

Otázka rovnosti těchto dvou tříd je považována za jeden z nejobtížnějších otevřených problémů v oblasti teoretické informatiky. Clay Mathematical Institute zařadil tento problém na svůj seznam problémů tisíciletí a za jeho vyřešení nabízí odměnu jeden milion amerických dolarů .

Viz také

Poznámky

↑ 1 2 Cormen, Thomas H.; Leizerson, Karel I.; Rivest, Ronald L.; Stein, Clifford. Algorithms: Construction and Analysis, 2nd edition = Introduction to Algorithms druhé vydání. - M .: "Williams" , 2005. - ISBN 5-8459-0857-4 .
↑ A. A. Zykov. Základy teorie grafů. - 3. vyd. - M . : Vuzovskaya kniga, 2004. - S. 10. - 664 s. — ISBN 5-9502-0057-8 .

Odkazy

Girsh EA " Výpočetní složitost a základy kryptografie " . Kurz přednášek popisující základy výpočetní složitosti a kryptografie.
Yuri Lifshits " Moderní problémy teoretické informatiky " . Kurz přednášek o algoritmech pro NP-těžké problémy.
A. A. Razborov . Teoretická informatika: pohled matematika // Computerra . - 2001. - č. 2 . (downlink)(alternativní odkaz)
A. A. RAZBOROV O složitosti výpočtů // Matematické vzdělání . - MTSNMO , 1999. - č. 3 . - S. 127-141 .

Slovníky a encyklopedie	Velký Rus

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY