From Wikipedia, the free encyclopedia
În informatică, complexitatea în timp a unui algoritm exprimă măsura timpului cât durează rularea algoritmului, ca funcție de lungimea șirului(d) ce reprezintă datele de intrare.[1]:226 Complexitatea în timp a unui algoritm este exprimată cel mai adesea folosind notația Big O, care exclude coeficienții și termenii de grad inferior. Când este exprimată astfel, se spune că complexitatea în timp este exprimată asimptotic, adică atunci când dimensiunea intrării tinde spre infinit. De exemplu, dacă durata de timp necesară unui algoritm pentru a rula pe intrări de dimensiune n este cel mult 5n3 + 3n pentru orice n (mai mare decât un n0), complexitatea asimptotică în timp este O(n3).
Complexitatea în timp este frecvent estimată prin numărarea operațiilor elementare efectuate de algoritm, unde o operație are o durată fixă. Astfel, timpul de rulare diferă de numărul de operații elementare cel mult printr-un factor constant.
Deoarece performanța unui algoritm timp poate varia cu diferite intrări de aceeași mărime, se utilizează frecvent complexitatea în timp în cel mai rău caz, notată cu T(n), valoare definită ca fiind cantitatea maximă de timp consumată dintre toate intrările de dimensiune n. Mai puțin frecvent, și, de obicei, specificată în mod explicit, este măsura complexității în cazul mediu. Complexitățile în timp sunt clasificate în funcție de natura funcției T(n). De exemplu, un algoritm cu T(n) = O(n) se numește algoritm în timp liniar, iar un algoritm cu T(n) = O(kn) pentru o constantă k>1 este numit algoritm în timp exponențial.
Următorul tabel rezumă unele clase de complexități în timp întâlnite frecvent. În tabel, poly(x) = xO(1), adică polinomial în x.
Nume | Clasă de complexitate | Timp de rulare (T(n)) | Exemple de timpi de rulare | Exemple de algoritmi |
---|---|---|---|---|
timp constant | O(1) | 10 | Determinarea dacă un număr întreg (reprezentat în binar) este par sau impar | |
timp invers Ackermann(d) | O(α(n)) | Timp amortizat(d) pe operație folosind structuri de date cu mulțimi disjuncte(d) | ||
timp logaritmic iterat | O(log* n) | Colorarea distribuită a ciclurilor | ||
log-logaritmic | O(log log n) | Timp amortizat pe operație când se folosește o coadă cu priorități(d) mărginită[2] | ||
timp logaritmic | DLOGTIME(d) | O(log n) | log n, log(n2) | Căutarea binară |
timp polilogaritmic | poly(log n) | (log n)2 | ||
putere fracționară | O(nc) unde 0 < c < 1 | n1/2, n2/3 | Căutarea într-un arbore kd(d) | |
timp liniar | O(n) | n | Găsirea celui mai mic sau a celui mai mare element dintr-un tablou(d) nesortat | |
timp "n log star n" | O(n log* n) | Algoritmul lui Seidel(d) de triangulare a poligonului. | ||
timp cvasiliniar | O(n log n) | n log n, log n! | Cea mai rapidă sortare prin comparație(d) posibilă; transformata Fourier rapidă(d). | |
timp pătratic | O(n2) | n2 | Bubble sort(d); Insertion sort(d); convoluția directă(d) | |
timp cubic | O(n3) | n3 | Înmulțirea naivă a două matrice n×n. Calculul corelării parțiale(d). | |
timp polinomial | P | 2O(log n) = poly(n) | n, n log n, n10 | Algoritmul lui Karmarkar(d) pentru programare liniară; testul de primalitate AKS(d) |
timp cvasipolinomial | QP | 2poly(log n) | nlog log n, nlog n | Cel mai bine cunoscut algoritm de aproximare(d) O(log2 n) pentru problema arborelui Steiner(d) orientată. |
timp subexponențial (prima definiție) | SUBEXP | O(2nε) oricare ar fi ε > 0 | O(2log nlog log n) | Presupunând drept adevărate conjecturile de teoria complexității, BPP(d) este inclusă în SUBEXP.[3] |
timp subexponențial (a doua definiție) | 2o(n) | 2n1/3 | Cel mai cunoscut algoritm de factorizarea întregilor și de izomorfism de grafuri(d) | |
timp exponențial (cu exponent liniar) | E(d) | 2O(n) | 1.1n, 10n | Rezolvarea problemei comis-voiajorului cu programare dinamică |
timp exponențial | EXPTIME(d) | 2poly(n) | 2n, 2n2 | Rezolvarea înmulțirilor în lanț ale matricilor(d) prin căutare cu forța brută(d) |
timp factorial | O(n!) | n! | Rezolvarea problemei comis-voiajorului prin căutare cu forța brută(d) | |
timp dublu exponențial | 2-EXPTIME(d) | 22poly(n) | 22n | Decizia privind valoarea de adevăr a unei afirmații din aritmetica Presburger(d) |
Se spune despre un algoritm că este în timp constant (sau timp O(1)) dacă valoarea lui T(n) este delimitată de o valoare care nu depinde de mărimea datelor de intrare. De exemplu, accesarea unui singur element într-un tablou(d) are nevoie de timp constant întrucât trebuie să fie efectuată o singură operațiune pentru a-l localiza. La fel și găsirea valorii minime într-un tablou sortat în ordine crescătoare – este primul element. Cu toate acestea, găsirea valorii minime într-un tablou neordonat nu este constantă de timp, întrucât este nevoie de o parcurgere a fiecărui element din tablou, în scopul de a determina valoarea minimă. Prin urmare, aceasta este o operațiune în timp liniar, care durează O(n). Dacă numărul de elemente este cunoscut în avans și nu se schimbă, cu toate acestea, un astfel de algoritm poate fi considerat a rula în timp constant.
În ciuda denumirii de „timp constant”, timpul de rulare nu trebuie să fie independent de dimensiunea problemei, ci o limită superioară a timpului de rulare trebuie să fie delimitată independent de dimensiunea problemei. De exemplu, taskul de a „schimba valorile a și b dacă este necesar, astfel încât a≤b” este considerat a rula în timp constant, chiar dacă durata efectivă poate depinde dacă este sau nu este deja adevărat că a ≤ b. Cu toate acestea, există unele constante t astfel încât timpul necesar este întotdeauna cel mult t.
Iată câteva exemple fragmente de cod care se execută în timp constant:
int index = 5; int item = lista[index]; if (condiție adevărată) then efectuează operațiunii care se execută în timp constant else efectuează alte operațiuni care se execută în timp constant for i = 1 to 100 for j = 1 to 200 efectuează operațiunii care se execută în timp constant
Dacă T(n) este O(orice valoare constantă), aceasta este echivalentă cu și enunțată în notație standard, T(n) = O(1).
Se spune că un algoritm este în timp logaritmic dacă T(n) = O(log n). Ca urmare a utilizării sistemului de numerație binar de către calculatoare, logaritmul este frecvent în bază 2 (log2 n, uneori scris lg n). Cu toate acestea, schimbarea bazei(d) pentru logaritmi, loga n și logb n diferă doar printr-o constantă multiplicativă, care în notație Big-O este eliminată; astfel că O(log n) este o notație standard pentru algoritmii în timp logaritmic, indiferent de baza logaritmului.
Algoritmii care au durata de execuție în timp logaritmic se întâlnesc de obicei în operații pe arbori binari sau atunci când se utilizează căutarea binară.
Un algoritm O(log n) este considerat extrem de eficient, deoarece numărul de operațiuni pe instanță necesar pentru a finaliza rularea scade la fiecare instanță.
Un exemplu foarte simplu de acest tip este un algoritmul care taie un șir în jumătate, apoi taie jumătatea din dreapta în jumătate, și așa mai departe. El va dura O(log n) (n fiind lungimea șirului) deoarece șirul se taie în jumătate înainte de fiecare tipărire (presupunând că console.log și str.substring rulează în timp constant).
Aceasta înseamnă că, pentru a crește numărul de tipăriri cu 1, trebuie dublată lungimea șirului.
// Function to recursively print the right half of a string
var right = function(str){
var length = str.length;
// Helper function
var help = function(index){
// Recursive Case: Print right half
if(index < length){
// Prints characters from index until the end of the array
console.log(str.substring(index, length));
// Recursive Call: call help on right half
help(Math.ceil((length + index)/2));
}
// Base Case: Do Nothing
}
help(0);
}
Un algoritm este considerat a fi în timp polilogaritmic dacă T(n) = O((log n)k), pentru un k constant. De exemplu, ordonarea lanțului de matrice poate fi rezolvată în timp polilogaritmic pe o mașină cu acces aleator paralel.
Se spune că un algoritm rulează în timp subliniar dacă T(n) = o(n). În particular, aici sunt incluși algoritmii cu complexitățile definite mai sus, precum și alții cum ar fi căutarea lui Grover(d) de complexitate O(n½).
Algoritmii tipici care sunt exacți și totuși rulează în timp subliniar folosesc prelucrări paralele (așa cum face algoritmul NC1 de calcul al determinantului matricei), prelucrări neclasice(d) (de exemplu, căutarea lui Grover), sau li se garantează unele presupuneri despre structura datelor de intrare (cum ar fi căutarea binară și mulți algoritmi de mentenanță a arborilor, care rulează în timp logaritmic). Limbajele formale însă, așa cum este mulțimea tuturor șirurilor care au un bit de 1 pe poziția indicată de primii log(n) biți ai șirului, ar putea depinde de toți biții intrării, dar tot ar putea fi calculați în timp subliniar.
Termenul specific algoritm în timp subliniar este de regulă rezervat algoritmilor diferiți de cei de mai sus prin aceea că sunt rulați peste modele seriale clasice de mașină și nu au dreptul la prezumții despre datele de intrare.[4] Ei pot însă să fie randomizați(d), și chia trebuie pentru orice task netrivial.
Cum un astfel de algoritm trebuie să dea un răspuns fără a-și citi datele de intrare în întregime, detaliile lui depind masiv de accesul permis asupra intrării. De regulă, pentru o intrare reprezentată de un șir binar b1,...,bk se presupune că algoritmul poate cere și primi într-un timp O(1) valoarea lui bi oricare ar fi i.
Algoritmii în timpi subliniari sunt de regulă randomizați și furnizează doar soluți aproximative(d). De fapt, se poate demonstra ușor că nu este decidabilă proprietatea unui șir binar de a avea doar zerouri (și niciun 1) printr-un algoritm neaproximativ în timp subliniar. Algoritmii în timpi subliniari apar natural în cercetarea testării proprietăților(d).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.