Complexitate exponențială

Complexitate exponențială - în teoria complexității algoritmilor , complexitatea problemei, limitată de exponențialul polinomului dimensiunii problemei, adică este limitată de funcția , unde este un polinom și este dimensiunea a problemei. În acest caz, se spune că complexitatea problemei crește exponențial . Adesea, complexitatea se referă la timpul de execuție al unui algoritm. În acest caz, se spune că algoritmul aparține clasei EXPTIME . Cu toate acestea, complexitatea se poate referi și la memorie sau la alte resurse necesare pentru ca algoritmul să funcționeze. $\exp(P(n))$ $P$ $n$

Distincția dintre algoritmii polinomi și exponențiali se întoarce la von Neumann . [unu]

Complexitatea timpului

Sarcinile cu complexitate exponențială de rulare formează clasa EXPTIME , definită formal ca:

{\text{EXPTIME}}=\bigcup _{k=1}^{\infty}TIME\left(2^{n^{k}}\right)

unde este ansamblul problemelor care pot fi rezolvate prin algoritmi al caror timp de rulare este delimitat de sus de functia . $TIME(f(n))$ $f(t)$

Comparație cu complexitatea polinomială

Este în general acceptat că algoritmii cu complexitate polinomială sunt „rapidi”, în timp ce algoritmii cu complexitate mai mare decât polinomială sunt „lenti”. Din acest punct de vedere, algoritmii cu complexitate exponențială sunt lenți. Cu toate acestea, această presupunere nu este în întregime corectă. Faptul este că timpul de rulare al algoritmului depinde de valoarea lui n (dimensiunea problemei) și de constantele asociate ascunse în notația O. În unele cazuri, pentru valori mici ale lui n , timpul polinomial poate depăși timpul exponențial. Cu toate acestea, pentru valori mari ale lui n , timpul de rulare al algoritmului cu complexitate exponențială este mult mai lung.

Complexitate subexponențială

Există algoritmi care rulează în timp mai mult decât polinomial ( "super-polinom" ), dar mai puțin decât timp exponențial ( "sub-exponențial" ). Un exemplu de astfel de problemă este factorizarea unui număr întreg în factori primi ( factorizare ). Astfel de algoritmi sunt denumiți și „lenti”.

Vezi și

Clasa EXPTIME
O notație
timp constant
Timp liniar
NP problemă completă

Note

↑ John von Neumann. Un anumit joc de două persoane cu sumă zero echivalent cu problema optimă de atribuire // Contribuții la teoria jocurilor / HW Kuhn , AW Tucker , Eds. — Princeton, NJ: Princeton Univ. Press , 1953. - P. 5-12. — 404 p.