Časová náročnost - Time complexity

Grafy funkcí běžně používaných při analýze algoritmů , ukazující počet operací N versus vstupní velikost n pro každou funkci

Ve vědě o počítačích je složitost doba je výpočetní složitost , který popisuje množství výpočetní čas potřebný ke spuštění algoritmu . Časová složitost se běžně odhaduje spočítáním počtu elementárních operací provedených algoritmem za předpokladu, že provedení každé elementární operace zabere určitý čas. Množství času a počet elementárních operací provedených algoritmem se tedy považuje za související s konstantním faktorem .

Protože doba běhu algoritmu se může u různých vstupů stejné velikosti lišit, běžně se uvažuje o časové složitosti nejhoršího případu , což je maximální doba potřebná pro vstupy dané velikosti. Méně častá a obvykle výslovně specifikovaná je složitost průměrného případu , což je průměr času zabraného vstupům dané velikosti (to dává smysl, protože možných vstupů dané velikosti je pouze konečný počet). V obou případech je časová složitost obecně vyjádřena jako funkce velikosti vstupu. Protože je tato funkce obecně obtížně přesně vypočítatelná a doba běhu pro malé vstupy obvykle není důsledná, obvykle se člověk zaměřuje na chování složitosti, když se velikost vstupu zvyšuje - tj. Na asymptotické chování složitosti. Proto je složitost doba je obvykle vyjádřena pomocí velký O notace , typicky , , , , atd, kde n je velikost v jednotkách bitů potřebných pro představují vstup.

Algoritmické složitosti jsou klasifikovány podle typu funkce vyskytující se ve velkém O notaci. Algoritmus s časovou složitostí je například lineární časový algoritmus a algoritmus s časovou složitostí pro nějakou konstantu je polynomiální časový algoritmus .

Tabulka běžných časových složitostí

Následující tabulka shrnuje některé třídy běžně se vyskytujících časových složitostí. V tabulce poly ( x ) = x O (1) , tj. Polynom v  x .

název Třída složitosti Doba chodu ( T ( n )) Příklady provozních dob Příklady algoritmů
konstantní čas O (1) 10 Nalezení střední hodnoty v seřazené řadě čísel

Výpočet (−1) n

inverzní Ackermannův čas O ( α ( n )) Amortizovaný čas na operaci pomocí disjunktní sady
iterovaný logaritmický čas O ( log *  n ) Distribuované barvení cyklů
log-logaritmická O (log log n ) Amortizovaný čas na operaci pomocí fronty s omezenou prioritou
logaritmický čas DLOGTIME O (log  n ) log  n , log ( n 2 ) Binární vyhledávání
polylogaritmický čas poly (log  n ) (log  n ) 2
zlomková síla O ( n c ) kde 0 < c <1 n 1/2 , n 2/3 Hledání v kd-stromu
lineární čas O ( n ) n , 2 n + 5 Hledání nejmenší nebo největší položky v netříděném poli , Kadaneův algoritmus , lineární vyhledávání
čas „n log-star n“ O ( n log * n ) Seidel je polygon triangulační algoritmus.
linearitmický čas O ( n log n ) n log n , log n ! Nejrychlejší možné srovnání ; Rychlá Fourierova transformace .
kvazilineární čas n poly (log n )
kvadratický čas O ( n 2 ) n 2 Bublinkové třídění ; Vkládací třídění ; Přímá konvoluce
kubický čas O ( n 3 ) n 3 Naivní násobení dvou n × n matic. Výpočet částečné korelace .
polynomiální čas P 2 O (log n ) = poly ( n ) n 2 + n , n 10 Karmarkarův algoritmus pro lineární programování ; Test primality AKS
kvazi-polynomický čas QP 2 poly (log  n ) n log log n , n log  n Nejznámější O (log 2 n )- aproximační algoritmus pro směrovaný problém Steinerova stromu .
subexponenciální čas
(první definice)
SUBEXP O (2 n ε ) pro všechna ε > 0 Obsahuje BPP, pokud se EXPTIME (viz níže) nerovná MA .
subexponenciální čas
(druhá definice)
2 o ( n ) 2 n 1/3 Nejznámější algoritmus pro celočíselnou faktorizaci ; dříve nejlepší algoritmus pro izomorfismus grafů
exponenciální čas
(s lineárním exponentem)
E 2 O ( n ) 1,1 n , 10 n Řešení problému cestujícího obchodníka pomocí dynamického programování
exponenciální čas EXPTIME 2 poly ( n ) 2 n , 2 n 2 Řešení násobení maticového řetězce pomocí vyhledávání hrubou silou
faktoriální čas O ( n !) n ! Řešení problému obchodního cestujícího pomocí vyhledávání hrubou silou
dvojnásobný exponenciální čas 2-EXPTIME 2 2 poly ( n ) 2 2 n Rozhodování o pravdivosti daného tvrzení v Presburgerově aritmetice

Konstantní čas

Algoritmus je považován za konstantní čas (také zapsaný jako čas O (1) ), pokud je hodnota T ( n ) ohraničena hodnotou, která nezávisí na velikosti vstupu. Například přístup k jakémukoli jednotlivému prvku v poli vyžaduje konstantní čas, protože k jeho lokalizaci je třeba provést pouze jednu operaci . Podobným způsobem nalezení minimální hodnoty v poli seřazeném vzestupně; je to první prvek. Nalezení minimální hodnoty v neuspořádaném poli však není operace s konstantním časem, protože ke stanovení minimální hodnoty je nutné skenovat každý prvek v poli. Jedná se tedy o lineární časovou operaci, která trvá čas O ( n ). Pokud je počet prvků předem znám a nemění se, lze přesto říci, že takový algoritmus běží v konstantním čase.

Navzdory názvu „konstantní čas“ nemusí být doba běhu nezávislá na velikosti problému, ale horní hranice doby běhu musí být ohraničena nezávisle na velikosti problému. Například úkol „v případě potřeby vyměňte hodnoty a a b tak, aby ab “ se nazývá konstantní čas, i když čas může záviset na tom, zda již platí, že ab . Existuje však nějaká konstanta t taková, že požadovaný čas je vždy nejvýše t .

Zde je několik příkladů fragmentů kódu, které běží v konstantním čase:

int index = 5;
int item = list[index];
if (condition true) then
    perform some operation that runs in constant time
else
    perform some other operation that runs in constant time
for i = 1 to 100
    for j = 1 to 200
        perform some operation that runs in constant time

Pokud T ( n ) je O ( jakákoli konstantní hodnota ), je to ekvivalentní a uvedeno ve standardním zápisu jako T ( n ) je O (1).

Logaritmický čas

Algoritmus říká, že zabere logaritmický čas, když T ( n ) = O (log n ) . Protože log a  n a log b  n jsou spojeny konstantním multiplikátorem a takový multiplikátor je pro klasifikaci velkých O irelevantní , standardní použití pro algoritmy s logaritmickým časem je O (log n ) bez ohledu na základnu logaritmu zobrazenou v exprese T .

Algoritmy využívající logaritmický čas se běžně vyskytují v operacích na binárních stromech nebo při použití binárního vyhledávání .

O (log n algoritmus) je považován za vysoce účinný, jako poměr počtu operací na velikost vstupu se snižuje a blíží nule, když n se zvyšuje. Algoritmus, který musí přistupovat ke všem prvkům svého vstupu, nemůže trvat logaritmický čas, protože čas potřebný ke čtení vstupu velikosti n je řádově n .

Příklad logaritmického času je dán hledáním ve slovníku. Uvažujme slovník D, který obsahuje n záznamů seřazených podle abecedy . Předpokládáme, že pro 1 ≤ kn lze přistupovat ke k -tému vstupu slovníku v konstantním čase. Nechť D ( k ) označuje tento k -tý záznam. Podle těchto hypotéz lze test, zda je slovo w ve slovníku, provést v logaritmickém čase: zvažte , kde označuje podlahovou funkci . Pokud , pak jsme hotovi. Else, pokud , pokračujte ve vyhledávání stejným způsobem v levé polovině slovníku, jinak pokračovat podobně s pravou polovinou slovníku. Tento algoritmus je podobný metodě, která se často používá k nalezení záznamu v papírovém slovníku.

Polylogaritmický čas

Algoritmus se říká, že běží v polylogaritmickém čase, pokud jeho čas T ( n ) je O ((log n ) k ) pro nějakou konstantu k . Dalším způsobem, jak to napsat, je O (log k n ) .

Například matrice řetězec uspořádání může být řešen v polylogarithmic čase na paralelní RAM stroj , a graf může být stanoveno, že planární v plně dynamickým způsobem v O (log 3 n ) krát za vkládání / mazání provozu.

Sublineární čas

Algoritmus se říká, že běží v sublineárním čase (často hláskovaný sublineární čas ), pokud T ( n ) = o ( n ) . Zejména to zahrnuje algoritmy s časovou složitostí definovanou výše.

Typické algoritmy, které jsou přesné a přesto běží v sublineárním čase, používají paralelní zpracování (jak to dělá výpočet determinantu matice NC 1 ), nebo alternativně mají zaručené předpoklady o vstupní struktuře (jak to dělá logaritmické časové binární vyhledávání a mnoho algoritmů pro údržbu stromů) . Nicméně, formální jazyky , jako množinu všech řetězců, které mají 1-bit v poloze uvedena první log ( n ) bity řetězce může záviset na každém kousku vstupu a přesto být vypočitatelný v sub-lineární čas.

Specifický termín algoritmus sublineárního času je obvykle vyhrazen pro algoritmy, které jsou na rozdíl od výše uvedených v tom, že jsou provozovány přes klasické modely sériových strojů a nejsou povoleny předchozí předpoklady na vstupu. Mohou však být randomizováni a skutečně musí být randomizováni pro všechny úkoly, kromě těch nejtriviálnějších.

Protože takový algoritmus musí poskytnout odpověď bez přečtení celého vstupu, jeho podrobnosti do značné míry závisí na přístupu povoleném vstupu. Obvykle pro vstup, který je reprezentován jako binární řetězec b 1 ,…, b k , se předpokládá, že algoritmus může v čase O (1) požadovat a získat hodnotu b i pro libovolné i .

Sublineární časové algoritmy jsou obvykle randomizované a poskytují pouze přibližná řešení. Vlastnost binárního řetězce, který má pouze nuly (a žádné), lze ve skutečnosti snadno dokázat jako nerozhodnutelnou (ne-přibližným) sublineárním časovým algoritmem. Sublineární časové algoritmy přirozeně vznikají při vyšetřování testování vlastností .

Lineární čas

Algoritmus říká, že potřebuje lineární čas nebo O ( n ) čas, pokud je jeho časová složitost O ( n ) . Neformálně to znamená, že doba běhu se zvyšuje maximálně lineárně s velikostí vstupu. Přesněji to znamená, že existuje konstanta c taková, že doba běhu je nanejvýš cn pro každý vstup velikosti n . Například postup, který sčítá všechny prvky seznamu, vyžaduje čas úměrný délce seznamu, pokud je čas přidání konstantní, nebo alespoň ohraničený konstantou.

Lineární čas je nejlepší možná časová složitost v situacích, kdy algoritmus musí postupně číst celý svůj vstup. Proto bylo investováno mnoho výzkumu do objevování algoritmů vykazujících lineární čas nebo přinejmenším téměř lineární čas. Tento výzkum zahrnuje softwarové i hardwarové metody. Existuje několik hardwarových technologií, které k zajištění toho využívají paralelismus . Příkladem je paměť adresovatelná podle obsahu . Tento koncept lineárního času se používá v řetězcových algoritmech, jako je algoritmus Boyer -Moore a Ukkonenův algoritmus .

Kvazilineární čas

Algoritmus se říká, že běží v kvazilineárním čase (také označovaném jako log-lineární čas ), pokud T ( n ) = O ( n log k n ) pro nějakou kladnou konstantu k ; lineitmický čas je případ k = 1 . Pomocí soft O notace jsou tyto algoritmy Õ ( n ). Kvazilineární časové algoritmy jsou také O ( n 1+ ε ) pro každou konstantu ε > 0, a běží tedy rychleji než jakýkoli polynomiální časový algoritmus, jehož časová hranice obsahuje termín n c pro jakékoli c > 1 .

Algoritmy, které běží v kvazilineárním čase, zahrnují:

V mnoha případech je doba běhu n log n jednoduše výsledkem provedení operace Θ (log n ) nkrát (notace viz Big O notation § Family of Bachmann – Landau notations ). Například binární třídění stromů vytvoří binární strom vložením každého prvku pole n -velikosti jeden po druhém. Protože operace vložení na binárním vyhledávacím stromu s vlastním vyvažováním trvá O (log n ), trvá celý algoritmus čas O ( n log n ) .

Porovnávací druhy vyžadují v nejhorším případě srovnání alespoň Ω ( n log n ), protože log ( n !) = Θ ( n log n ) , podle Stirlingovy aproximace . Často také vznikají ze vztahu rekurence T ( n ) = 2 T ( n /2) + O ( n ) .

Sub-kvadratický čas

Algoritmus se říká, že subquadratic čas v případě, T ( n ) = O ( N 2 ) .

Například jednoduché, srovnávací algoritmy řazení jsou kvadratické (např. Vkládací řazení ), ale lze nalézt pokročilejší algoritmy, které jsou subkvadratické (např. Skořepinové řazení ). V lineárním čase neprobíhá žádné obecné použití, ale změna z kvadratického na subkvadratický má velký praktický význam.

Polynomiální čas

Algoritmus se říká, že z polynomial čase , pokud jeho provozní čas horní ohraničen prostřednictvím polynomu expresí v velikost vstupu pro algoritmus, který je, T ( n ) = O ( n k ) pro některé pozitivní konstantní k . Problémy, pro které existuje deterministický polynomiální časový algoritmus, patří do třídy složitosti P , která je ústřední v oblasti teorie výpočetní složitosti . Cobhamova práce uvádí, že polynomiální čas je synonymem pro „traktovatelný“, „proveditelný“, „efektivní“ nebo „rychlý“.

Několik příkladů polynomiálních časových algoritmů:

  • Výběr třídění třídění algoritmus na n celků provádí operace pro nějakou konstantu A . Běží tedy v čase a je to polynomiální časový algoritmus.
  • Všechny základní aritmetické operace (sčítání, odčítání, násobení, dělení a porovnávání) lze provádět v polynomiálním čase.
  • Maximální shody v grafech lze nalézt v polynomiálním čase.

Silně a slabě polynomický čas

V některých kontextech, zvláště při optimalizaci , se rozlišuje mezi silně polynomiálním časovým a slabě polynomiálním časovým algoritmem. Tyto dva pojmy jsou relevantní pouze v případě, že vstupy do algoritmů sestávají z celých čísel.

V aritmetickém modelu výpočtu je definován silně polynomiální čas. V tomto modelu výpočtu základní aritmetické operace (sčítání, odčítání, násobení, dělení a porovnávání) provádějí krok za jednotku času bez ohledu na velikosti operandů. Algoritmus běží v silně polynomiálním čase, pokud:

  1. počet operací v aritmetickém modelu výpočtu je ohraničen polynomem v počtu celých čísel ve vstupní instanci; a
  2. prostor použitý algoritmem je ohraničen polynomem velikosti vstupu.

Jakýkoli algoritmus s těmito dvěma vlastnostmi lze převést na polynomiální časový algoritmus nahrazením aritmetických operací vhodnými algoritmy pro provádění aritmetických operací na Turingově stroji . Pokud není splněn druhý z výše uvedených požadavků, pak to již není pravda. Vzhledem k celému číslu (které zabírá místo úměrné n v modelu Turingova stroje) je možné počítat s n násobením pomocí opakovaného kvadratury . Prostor použitý k reprezentaci je však v prostoru použitém k reprezentaci vstupu úměrný , a tedy spíše exponenciální než polynomický. Z tohoto důvodu není možné tento výpočet provádět v polynomiálním čase na Turingově stroji, ale je možné jej polynomicky vypočítat mnoha aritmetickými operacemi.

Naopak existují algoritmy, které běží v řadě kroků Turingova stroje ohraničených polynomem v délce binárně kódovaného vstupu, ale nevyžadují řadu aritmetických operací ohraničených polynomem v počtu vstupních čísel. Euclidean algoritmus pro výpočet největšího společného dělitele dvou celých čísel je jedním z příkladů. Vzhledem k tomu, že dvě celá čísla a , algoritmus provádí aritmetické operace s čísly s nejvýše bity. Počet aritmetických operací přitom nemůže být ohraničen počtem celých čísel na vstupu (což je v tomto případě konstantní, na vstupu jsou vždy pouze dvě celá čísla). Vzhledem k poslednímu pozorování algoritmus neběží v silně polynomiálním čase. Jeho skutečná doba provozu závisí na tom, velikostem a nejen na počtu čísel ve vstupu.

Algoritmus, který běží v polynomiálním čase, ale není silně polynomický, se říká, že běží ve slabě polynomickém čase . Známým příkladem problému, pro který je znám algoritmus slabě polynomiálního času, ale není známo, že by připustil silně polynomiální časový algoritmus, je lineární programování . Slabě polynomický čas by neměl být zaměňován s pseudopolynomiálním časem .

Třídy složitosti

Pojem polynomiálního času vede v teorii výpočetní složitosti k několika třídám složitosti. Některé důležité třídy definované pomocí polynomiálního času jsou následující.

P Třída složitosti z rozhodovacích problémů , které mohou být řešeny na deterministický Turing stroj v polynomiálním čase
NP Třída složitosti rozhodovacích problémů, které lze vyřešit na nedeterministickém Turingově stroji v polynomiálním čase
ZPP Třída složitosti rozhodovacích problémů, které lze vyřešit s nulovou chybou na pravděpodobnostním Turingově stroji v polynomiálním čase
RP Třída složitosti rozhodovacích problémů, které lze vyřešit pomocí jednostranné chyby na pravděpodobnostním Turingově stroji v polynomiálním čase.
BPP Třída složitosti rozhodovacích problémů, které lze vyřešit oboustrannou chybou na pravděpodobnostním Turingově stroji v polynomiálním čase
BQP Třída složitosti rozhodovacích problémů, které lze vyřešit oboustrannou chybou na kvantovém Turingově stroji v polynomiálním čase

P je nejmenší časově náročná třída na deterministickém stroji, který je robustní, pokud jde o změny modelu stroje. (Například změna z jednopáskového Turingova stroje na vícepáskový stroj může vést ke kvadratickému zrychlení, ale jakýkoli algoritmus, který běží v polynomiálním čase pod jedním modelem, to dělá i na druhém.) Jakýkoli daný abstraktní stroj bude mají třídu složitosti odpovídající problémům, které lze na tomto stroji vyřešit v polynomiálním čase.

Superpolynomiální čas

Algoritmus říká, že trvá superpolynomiální čas, pokud T ( n ) není ohraničeno výše žádným polynomem. Při použití malého počtu omega je to ω ( n c ) čas pro všechny konstanty c , kde n je vstupní parametr, typicky počet bitů na vstupu.

Například algoritmus, který běží na 2 n krocích na vstupu velikosti n, vyžaduje superpolynomiální čas (konkrétněji exponenciální čas).

Algoritmus, který využívá exponenciální zdroje, je jasně superpolynomiální, ale některé algoritmy jsou jen velmi slabě superpolynomiální. Například, Adleman-Pomerance-Rumely primality zkušební dráhy pro n O (log log n ) na čase na n- bitové vstupů; toto roste rychleji než jakýkoli polynom pro dostatečně velké n , ale vstupní velikost musí být neprakticky velká, než ji nebude moci ovládat polynom s malým stupněm.

Algoritmus, který vyžaduje superpolynomial čas leží mimo třída složitosti P . Cobhamova práce předpokládá, že tyto algoritmy jsou nepraktické a v mnoha případech jsou. Vzhledem k tomu, že problém P versus NP není vyřešen, není známo, zda problémy úplné NP vyžadují superpolynomiální čas.

Kvazi-polynomický čas

Kvazi-polynomiální časové algoritmy jsou algoritmy, které běží déle než polynomický čas, ale ne tak dlouho, aby byly exponenciálním časem. Nejhorší doba běhu kvazi-polynomického časového algoritmu je pro některé pevná . Neboť dostaneme polynomiální časový algoritmus, protože dostaneme sublineární časový algoritmus.

Kvazi-polynomiální časové algoritmy obvykle vznikají při redukci z NP-tvrdého problému na jiný problém. Například můžeme vzít instanci těžkého problému NP, řekněme 3SAT , a převést ji na instanci jiného problému B, ale velikost instance se stane . V takovém případě toto snížení nedokazuje, že problém B je NP-tvrdý; toto snížení pouze ukazuje, že neexistuje žádný polynomiální časový algoritmus pro B, pokud neexistuje kvazi-polynomiální časový algoritmus pro 3SAT (a tedy pro všechny NP ). Podobně existují problémy, pro které známe kvazi-polynomiální časové algoritmy, ale není znám žádný polynomiální časový algoritmus. Takové problémy vznikají v aproximačních algoritmech; slavným příkladem je směrovaný Steinerův stromový problém , pro který existuje kvazi-polynomický algoritmus aproximace času dosahující přibližného faktoru ( n je počet vrcholů), ale ukázat existenci takového polynomiálního časového algoritmu je otevřený problém.

Jiné výpočetní problémy s kvazi-polynomiálním časovým řešením, ale žádné známé polynomiální časové řešení, zahrnují problém zasazené kliky, ve kterém je cílem najít velkou kliku ve spojení kliky a náhodného grafu . Ačkoli je to kvazi-polynomiálně řešitelný, předpokládalo se, že problém zasazené kliky nemá žádné polynomiální časové řešení; tato zasadená klikací domněnka byla použita jako předpoklad výpočetní tvrdosti k prokázání obtížnosti několika dalších problémů v oblasti výpočetní teorie her , testování vlastností a strojového učení .

Třída složitosti QP se skládá ze všech problémů, které mají kvazi-polynomiální časové algoritmy. Lze jej definovat z hlediska DTIME následujícím způsobem.

Vztah k NP-úplným problémům

V teorii složitosti se nevyřešený problém P versus NP ptá, zda všechny problémy v NP mají algoritmy s polynomiálním časem. Všechny nejznámější algoritmy pro NP-úplné problémy jako 3SAT atd. Trvají exponenciálně. Skutečně se u mnoha přirozených NP-úplných problémů předpokládá, že nemají subexponenciální časové algoritmy. Zde „subexponenciální čas“ znamená druhou definici uvedenou níže. (Na druhou stranu, mnoho grafových problémů reprezentovaných přirozenou cestou maticemi sousednosti je řešitelných v subexponenciálním čase jednoduše proto, že velikost vstupu je druhou mocninou počtu vrcholů.) Tato domněnka (pro problém k-SAT) je známá jako hypotéza exponenciálního času . Protože se předpokládá, že NP-úplné problémy nemají kvazi-polynomiální časové algoritmy, některé výsledky nepřibližnosti v oblasti aproximačních algoritmů činí předpoklad, že NP-úplné problémy nemají kvazi-polynomiální časové algoritmy. Podívejte se například na známé výsledky nedostupnosti problému s krytem sady .

Subexponenciální čas

Termín subexponenciální čas se používá k vyjádření, že doba běhu některého algoritmu může růst rychleji než jakýkoli polynom, ale stále je výrazně menší než exponenciální. V tomto smyslu jsou problémy, které mají subexponenciální časové algoritmy, o něco obtížnější než ty, které mají pouze exponenciální algoritmy. Přesná definice „subexponenciální“ není obecně dohodnuta a níže uvádíme dvě nejpoužívanější.

První definice

Říká se, že problém je řešitelný v subexponenciálním čase, pokud jej lze vyřešit v běhových časech, jejichž logaritmy rostou menší než daný polynom. Přesněji řečeno, problém je v subexponenciálním čase, pokud pro každé ε > 0 existuje algoritmus, který řeší problém v čase O (2 n ε ). Souborem všech těchto problémů je třída složitosti SUBEXP, kterou lze definovat z hlediska DTIME následujícím způsobem.

Tento pojem subexponenciálu není z hlediska ε jednotný v tom smyslu, že ε není součástí vstupu a každé ε může mít svůj vlastní algoritmus pro daný problém.

Druhá definice

Někteří autoři definují subexponenciální čas jako doby běhu ve 2 o ( n ) . Tato definice umožňuje delší doby běhu než první definice subexponenciálního času. Příkladem takového subexponenciálního časového algoritmu je nejznámější klasický algoritmus pro celočíselnou faktorizaci, obecné síto číselného pole , které běží přibližně v čase , přičemž délka vstupu je n . Dalším příkladem byl problém isomorfismu grafu , který nejznámější algoritmus od roku 1982 do roku 2016 řešil v . Na STOC 2016 však byl představen kvazi-polynomiální časový algoritmus.

Je rozdíl, zda může být algoritmus subexponenciální ve velikosti instance, počtu vrcholů nebo počtu hran. V parametrizované složitosti , tento rozdíl je explicitní tím, že zvažuje párů z rozhodovacích problémů a parametry k . SUBEPT je třída všech parametrizovaných problémů, které běží v čase subexponenciálně v k a polynom ve vstupní velikosti n :

Přesněji řečeno, SUBEPT je třída všech parametrických problémů , u nichž je vypočitatelný funkce s a algoritmus, který rozhodne L v čase .

Exponenciální časová hypotéza

Exponenciální doba hypotéza ( ETH ), je to, že 3SAT , problém splnitelnost booleovských vzorců v konjunktivní normální formě s nejvýše tři literály za ustanovení a s n proměnné, nemůže být vyřešen v čase 2, O ( n ) . Přesněji řečeno, hypotéza je, že existuje nějaká absolutní konstanta c > 0 taková, že 3SAT nelze rozhodnout v čase 2 cn žádným deterministickým Turingovým strojem. S m označujícím počet klauzulí je ETH ekvivalentní hypotéze, že k SAT nelze vyřešit v čase 2 o ( m ) pro jakékoli celé číslo k ≥ 3 . Hypotéza exponenciálního času implikuje P ≠ NP .

Exponenciální čas

Algoritmus je považován za exponenciální čas , pokud T ( n ) je horní ohraničeno 2 poly ( n ) , kde poly ( n ) je nějaký polynom v n . Formálněji je algoritmus exponenciální čas, pokud T ( n ) je ohraničen O (2 n k ) pro nějakou konstantu k . Problémy, které připouštějí exponenciální časové algoritmy na deterministickém Turingově stroji, tvoří třídu složitosti známou jako EXP .

Někdy se exponenciální čas používá k označení algoritmů, které mají T ( n ) = 2 O ( n ) , kde exponent je nanejvýš lineární funkce n . To vede ke složitosti třídy E .

Faktoriální čas

Příkladem algoritmu, který běží ve faktoriálním čase, je bogosort , notoricky neefektivní algoritmus řazení založený na pokusu a omylu . Stupid sort třídí seznam n bodů opakovaným míchání seznamu, dokud není zjištěno, že třídit. V průměrném případě každý průchod algoritmem bogosort prozkoumá jedno z n ! objednání n položek. Pokud jsou položky odlišné, je seřazeno pouze jedno takové uspořádání. Bogosort sdílí dědictví s nekonečnou opičí větou .

Dvojnásobný exponenciální čas

Algoritmus je považován za dvojnásobný exponenciální čas, pokud T ( n ) je horní ohraničeno 2 2 poly ( n ) , kde poly ( n ) je nějaký polynom v n . Tyto algoritmy patří do třídy složitosti 2-EXPTIME .

Mezi známé dvojité exponenciální časové algoritmy patří:

Viz také

Reference