Notația Big O
From Wikipedia, the free encyclopedia
Notația Big O este o notație matematică care descrie comportamentul la limită(d) al unei funcții atunci când argumentul tinde la o anumită valoare sau la infinit. Este una din notațiile inventate de Paul Bachmann,[1] Edmund Landau(d),[2] și alții, numite colectiv notațiile Bachmann-Landau sau notațiile asimptotice.
În informatică, notația Big O este folosită pentru a clasifica algoritmii în funcție de felul în care timpul lor de rulare sau cerințele lor de spațiu cresc pe măsură ce crește dimensiunea datelor de intrare.[3] În teoria analitică a numerelor(d), notația Big O este adesea folosită pentru a exprima o legătură între diferența dintre o funcție aritmetică(d) și o aproximare mai bine înțeleasă; un exemplu celebru de astfel de diferență este termenul rest din teorema numerelor prime.
Notatia Big O caracterizează funcțiile după de vitezele lor de creștere: funcții diferite cu aceeași viteză de creștere pot fi reprezentate folosind aceeași notație O.
Litera O este folosită deoarece viteza de creștere a unei funcții este numită și ordin al funcției. O descriere a unei funcții în ceea ce privește notația Big O, de obicei, oferă doar o limită superioară(d) a vitezei de creștere a funcției. Cu notația Big O mai sunt asociate mai multe alte notații, folosind simbolurile o, Ω, ω, și Θ, pentru a descrie alte tipuri de limite ale vitezelor de creștere asimptotică.
Notația Big O este folosită și în multe alte domenii pentru a furniza estimări similare.