miniatura|300x300px| Exemplu de notație Big O: ∈ O () deoarece există (de exemplu, ) și (de exemplu, ) astfel încât ≤ pentru orice . Notația Big O este o notație matematică care descrie 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, , ș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. În teoria analitică a numerelor, notația Big O este adesea folosită pentru a exprima o legătură între diferența dintre o ș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 a vitezei de creștere a funcției. Cu notația Big O mai sunt asociate mai multe alte notații, folosind simbolurile ș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.
Definiție formală Fie o funcție cu valori reale sau complexe și o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale mulțimii numerelor reale pozitive, astfel încât să fie strict pozitivă pentru toate valorile suficient de mari ale lui . Se scrie
dacă și numai dacă pentru toate valorile suficient de mari ale lui , valoarea absolută a lui este cel mult un multiplu constant pozitiv al lui . Adică, dacă și numai dacă există un număr real pozitiv M și un număr real astfel încât
În multe contexte, ipoteza că suntem interesați de viteza de creștere când variabila tinde la infinit este lăsată nestabilită, și se scrie mai simplu că
Notația poate fi folosită și pentru a descrie comportamentul lui în preajma unui număr real (adesea, ): se spune
dacă și numai dacă există numere pozitive și astfel încât
Întrucât este aleasă în așa fel încât să fie nenulă, pentru valori ale lui de , ambele aceste definiții pot fi unificate folosind :
dacă și numai dacă
Exemplu În uzul tipic, definiția oficială a notației O nu este folosită direct; mai degrabă, notația O pentru o funcție se deduce din următoarele reguli de simplificare:
Dacă este o sumă de câțiva termeni, dacă există unul cu cea mai mare viteză de creștere, el poate fi păstrat și toți ceilalți omiși. Dacă este un produs al mai multor factori, orice constantă (termen din produs care nu depinde de ) poate fi omisă.
De exemplu, fie și se presupune că se dorește simplificarea acestei funcții, folosind notația O, pentru a descrie viteza de creștere a acesteia când tinde la infinit. Această funcție este suma a trei termeni: , și . Din cei trei termeni, cel cu cea mai mare viteză de creștere este cel cu cel mai mare exponent în funcție de , și anume . Acum se poate aplica a doua regulă: este un produs de 6 și în care primul factor nu depinde de . Omiterea acestui factor are ca rezultat forma simplificată . Astfel, spunem că este un „big-O” al lui (). Matematic, putem scrie . Se poate confirma acest calcul folosind definiția formală: fie și . Aplicând definiția formală de mai sus, afirmația că este echivalentă cu dezvoltarea sa,
pentru un și un aleși adecvat și pentru orice . Pentru a demonstra acest lucru, fie și . Atunci, pentru orice :
așa că
Utilizare Notația Big O are două domenii principale de aplicare:
în matematică , este utilizată în mod obișnuit pentru a descrie cât de aproape este o serie finită aproximând o anumită funcție, în special în cazul unei serii Taylor trunchiate sau al unei în domeniul informaticii, este utilă în analiza algoritmilor
În ambele aplicații, funcția care apare în cadrul lui O (...) este de obicei aleasă așa încât să fie cât mai simplă posibil, omițând factori constanți și termeni de ordin inferior.
Există două utilizări formale apropiate, dar cu totul diferite, ale acestei notații:
asimptotica infinită asimptotica infinitezimală.
Distincția aceasta există doar în practică, nu și în principiu definiția formală pentru „big O” este aceeași pentru ambele cazuri, cu limite diferite pentru argumentul funcției.
Asimptotica infinită miniatura| Graficele funcțiilor utilizate în mod obișnuit în analiza algoritmilor, care arată numărul de operații în raport cu dimensiunea intrării pentru fiecare funcție Notația Big O este utilă atunci când se . De exemplu, timpul (sau numărul de pași) necesar pentru a rezolva o problemă de dimensiune poate fi găsit a fi . Când crește foarte mult, termenul ajunge să domine, astfel încât toți ceilalți termeni pot fi neglijați, de exemplu, atunci când , termenul este de 1000 de ori mai mare ca termenul . Ignorarea acestuia din urmă ar avea un efect neglijabil asupra valorii expresiei pentru cele mai multe scopuri. Mai mult, coeficienții devin irelevanți dacă comparăm cu oricare alt ordin al expresiei, cum ar fi o expresie care conține un termen sau . Chiar dacă , dacă , acesta din urmă îl va depăși întotdeauna pe primul când crește mai mare decât 1.000.000 (). În plus, numărul de pași depinde de detaliile modelului mașinii pe care rulează algoritmul, dar diferite tipuri de mașini variază de obicei doar printr-un factor constant în numărul de pași necesari pentru executarea unui algoritm. Deci, notația Big O surprinde ceea ce rămâne: se scrie fie
fie
și se spune că algoritmul are complexitate de ordinul lui . Egalul nu mai reprezintă aici egalitate în sensul matematic normal, ci mai degrabă un „este“ mai popular, astfel încât a doua expresie este uneori considerată mai precisă (a se vedea discuția de mai jos despre semnul egal) în timp ce prima este considerată de unii ca un .
Asimptotica infinitezimală Big O poate fi folosită și pentru a descrie termenul de eroare într-o aproximare a unei funcții matematice. Termenii cei mai semnificativi sunt scriși explicit, iar termenii cel mai puțin semnificativi sunt rezumați într-un singur termen Big O. Considerăm, de exemplu, și două expresii ale acesteia care sunt valabile atunci când este mic:
Cea de a doua expresie (cea cu ) înseamnă că valoarea absolută a erorii este de cel mult o constantă înmulțită cu când este suficient de aproape de 0.
Proprietăți Dacă funcția poate fi scrisă ca o sumă finită a altor funcții, atunci cea mai rapidă creștere determină ordinul lui . De exemplu,
În special, dacă o funcție poate fi legată de un polinom în , atunci când tinde spre infinit, se pot ignora termenii de grad mai mic ai polinomului. De asemenea, mulțimile și sunt foarte diferiți. Dacă c este mai mare decât unu, atunci acesta crește mult mai repede. O funcție care crește mai repede decât pentru oricare se numește superpolinomială. Una care crește mai lent decât orice funcție exponențială de forma se numește subexponențială. Un algoritm poate necesita timp atât superpolimonial cât și subexponențial; printre astfel de exemple se numără algoritmii cei mai rapizi cunoscuți pentru factorizarea numerelor întregi și funcția .
Se poate ignora orice putere a lui din interiorul logaritmilor. Mulțimea este exact același cu . Logaritmii diferă numai printr-un factor constant (întrucât ) și astfel notația Big O ignoră termenul. Similar, logaritmii cu diferite baze constante sunt echivalenți. Pe de altă parte, exponențialele cu baze diferite nu sunt de același ordin. De exemplu, nu este același lucru cu .
Schimbarea unităților poate sau nu poate afecta ordinul algoritmului rezultat. Modificarea unităților este echivalentă cu înmulțirea variabilei corespunzătoare cu o constantă oriunde apare. De exemplu, dacă un algoritm rulează în timp de ordinul lui , înlocuirea cu înseamnă că algoritmul rulează în timp de ordinul lui , iar notația Big O ignoră constanta . Aceasta se poate scrie ca . Dacă, totuși, un algoritm rulează în timp de ordinul lui , înlocuirea lui cu dă timp de ordinul . Aceasta nu este echivalentă cu în general. Schimbarea variabilelor poate afecta, de asemenea, ordinul algoritmului rezultat. De exemplu, dacă timpul de execuție al algoritmului este atunci când este măsurat în termeni de număr de cifre al unui număr de intrare , timpul său de execuție este ca funcție de numărul de intrare x însuși, deoarece .
Produsul
Suma
Aceasta înseamnă că , ceea ce înseamnă că este un con convex.
Înmulțirea cu o constantă
Fie o constantă. Atunci: dacă este nenul.
Mai multe variabile Big O (și little o, Ω, etc.) pot fi utilizate și cu mai multe variabile. Pentru a defini Big O în mod formal pentru mai multe variabile, se presupune că și sunt două funcții definite pe o anumită submulțime a lui . Se spune că
dacă și numai dacă
În mod echivalent, condiția pentru unii poate fi înlocuită cu condiția , unde cu se notează . De exemplu, afirmația
spune că există constantele și astfel încât
unde se definește ca
Această definiție permite ca toate componentele lui să crească până la infinit. În special, afirmația
(de exemplu, ) este destul de diferită de
(de exemplu, ).
Sub această definiție, submulțimea pe care este definită o funcție este semnificativă atunci când se generalizează afirmațiile de la contextul univariabilă la cel multivariabilă. De exemplu, dacă și , atunci dacă se restrâng și la , dar nu dacă acestea sunt definite pe .
Aceasta nu este singura generalizare a notației Big O la funcții multivariabilă, dar în practică există o oarecare inconsistență în alegerea definiției.
Chestiuni de notație
Semnul egal Afirmația este , așa cum este definită mai sus, se scrie de obicei ca . Unii consideră că acest lucru este un , deoarece utilizarea semnului egal ar putea fi înșelătoare, deoarece sugerează o simetrie, pe care această afirmație nu o are. După cum spune , este adevărat că , dar nu și că . Knuth denumește astfel de afirmații „egalități unidirecționale”, deoarece dacă s-ar inversa cele două părți, „am putea deduce lucruri ridicole cum ar fi din identitățile și .”
Din aceste motive, ar fi mai precis să folosim și să scriem , considerând ca clasă a tuturor funcțiilor astfel încât pentru o constantă . Cu toate acestea, utilizarea semnului egal este obișnuită. Knuth a subliniat că „matematicienii folosesc în mod obișnuit semnul = așa cum folosesc cuvântul «este» în limba engleză: Aristotel este un om, dar un om nu este neapărat Aristotel.” (Unabridged version )
Alți operatori aritmetici Notația Big O poate fi utilizată și în combinație cu alți operatori aritmetici în ecuații mai complicate. De exemplu, cu se notează colecția de funcții având creșterea plus o parte a cărei creștere este limitată la . Prin urmare,
exprimă același lucru ca și
Exemplu Să presupunem că se dezvoltă un algoritm care să funcționeze pe o mulțime de elemente. Dezvoltatorii săi sunt interesați să găsească o funcție care să exprime cât timp va dura rularea algoritmului (în unele măsurători arbitrare ale timpului) în termeni de număr de elemente din mulțimea de intrare. Algoritmul funcționează apelând mai întâi o subrutină pentru sortarea elementelor din mulțime și efectuarea propriilor operații. Sortarea are o complexitate în timp cunoscută de , iar după executarea subrutinei algoritmul trebuie să mai ruleze încă pași înainte de a se termina. Astfel, complexitatea în timp a algoritmului poate fi exprimată ca Aici termenii sunt subsumați în cadrul lui cu creștere mai rapidă. Din nou, această utilizare ignoră o parte din semnificația formală a simbolului „=”, dar permite utilizarea notației Big O ca un substitut convenabil.
Utilizări multiple