Ce știm că nu știm despre algoritmi? (II)
Informaticienii și-au dat seama rapid că unele probleme sunt dificil de rezolvat, indiferent de progresele tehnologice ale puterii de calcul. În analiza algoritmilor, notația Big O a devenit cel mai utilizat standard de măsurare a complexității și a fost introdusă în anii ‚70 de Donald Knuth, autorul celebrei cărți: The Art of Computer Programming. În general, notația Big O măsoară scenariul cel mai pesimist pentru modul în care crește timpul de execuție sau consumul de memorie în funcție de dimensiunea datelor de intrare. De exemplu, complexitatea algoritmului GCD este O(log(min(a, b)). Prin comparație, căutarea într-o arie cu n elemente are o complexitate O(n), deoarece numărul de pași - în cel mai rău caz - crește proporțional cu dimensiunea tabloului. Cu toate acestea, extragerea unui element din arie are o complexitate de O(1), presupunând că știm indicele elementului pe care îl căutăm. Programele „Hello world” au o complexitate constantă O(1), iar algoritmii Divide et Impera pot reduce complexitatea lineară O(n) la o complexitate logaritmică O(log n), deoarece nu toate subproblemele vor fi evaluate.





































