Notația Big O

Exemplu de notație Big O: Format:Color ∈ O (Format:Color) deoarece există Format:Math (de exemplu, Format:Math) și Format:Math (de exemplu, Format:Math) astfel încât Format:Color ≤ Format:Math pentru orice Format:Math.

Notația Big O este o notație matematică care descrie Format:Ill-wd 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, Format:Ill-wd, ș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 Format:Ill-wd ș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 Format:Ill-wd a vitezei de creștere a funcției. Cu notația Big O mai sunt asociate mai multe alte notații, folosind simbolurile Format:Math și Format:Math, 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 Format:Math o funcție cu valori reale sau complexe și Format:Math o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale mulțimii numerelor reale pozitive, astfel încât Format:Math să fie strict pozitivă pentru toate valorile suficient de mari ale lui Format:Math. Se scrie

$f(x)=O(g(x))\text{ când }x\to \mathrm{\infty }$

dacă și numai dacă pentru toate valorile suficient de mari ale lui Format:Math, valoarea absolută a lui Format:Math este cel mult un multiplu constant pozitiv al lui Format:Math. Adică, Format:Math dacă și numai dacă există un număr real pozitiv M și un număr real Format:Math astfel încât

$|f(x)|\le Mg(x)\text{ pentru orice }x\ge x_0.$

În multe contexte, ipoteza că suntem interesați de viteza de creștere când variabila Format:Math tinde la infinit este lăsată nestabilită, și se scrie mai simplu că

$f(x)=O(g(x)).$

Notația poate fi folosită și pentru a descrie comportamentul lui Format:Math în preajma unui număr real Format:Math (adesea, Format:Math): se spune

$f(x)=O(g(x))\text{ când }x\to a$

dacă și numai dacă există numere pozitive Format:Math și Format:Math astfel încât

$|f(x)|\le Mg(x)\text{ când }0<|x-a|<\delta .$

Întrucât Format:Math este aleasă în așa fel încât să fie nenulă, pentru valori ale lui Format:Math Format:Ill-wd de Format:Math, ambele aceste definiții pot fi unificate folosind Format:Ill-wd:

$f(x)=O(g(x))\text{ când }x\to a$

dacă și numai dacă

$\underset{x\to a}{\mathrm{lim\; sup}}\left|\frac{f(x)}{g(x)}\right|<\mathrm{\infty }.$

Exemplu

În uzul tipic, definiția oficială a notației O nu este folosită direct; mai degrabă, notația O pentru o funcție Format:Math se deduce din următoarele reguli de simplificare:

• Dacă Format:Math 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ă Format:Math este un produs al mai multor factori, orice constantă (termen din produs care nu depinde de Format:Math) poate fi omisă.

De exemplu, fie Format:Math ș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 Format:Math tinde la infinit. Această funcție este suma a trei termeni: Format:Math, Format:Math și Format:Math. Din cei trei termeni, cel cu cea mai mare viteză de creștere este cel cu cel mai mare exponent în funcție de Format:Math, și anume Format:Math. Acum se poate aplica a doua regulă: Format:Math este un produs de 6 și Format:Math în care primul factor nu depinde de Format:Math. Omiterea acestui factor are ca rezultat forma simplificată Format:Math. Astfel, spunem că Format:Math este un „big-O” al lui (Format:Math). Matematic, putem scrie Format:Math. Se poate confirma acest calcul folosind definiția formală: fie Format:Math și Format:Math. Aplicând definiția formală de mai sus, afirmația că Format:Math este echivalentă cu dezvoltarea sa,

$|f(x)|\le M{x}^4$

pentru un Format:Math și un Format:Math aleși adecvat și pentru orice Format:Math. Pentru a demonstra acest lucru, fie Format:Math și Format:Math. Atunci, pentru orice Format:Math:

$\begin{array}{cc}|6x^4-2x^3+5|& \le 6x^4+|2x^3|+5\\ & \le 6x^4+2x^4+5x^4\\ & =13x^4\end{array}$

așa că

$|6x^4-2x^3+5|\le 13x^4.$

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 Format:Ill-wd
• în domeniul informaticii, este utilă în analiza algoritmilor

În ambele aplicații, funcția Format:Math 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 principiuFormat:Mdash definiția formală pentru „big O” este aceeași pentru ambele cazuri, cu limite diferite pentru argumentul funcției.

Asimptotica infinită

Graficele funcțiilor utilizate în mod obișnuit în analiza algoritmilor, care arată numărul de operații Format:Math în raport cu dimensiunea intrării Format:Math pentru fiecare funcție

Notația Big O este utilă atunci când se Format:Ill-wd. De exemplu, timpul (sau numărul de pași) necesar pentru a rezolva o problemă de dimensiune Format:Math poate fi găsit a fi Format:Math. Când Format:Math crește foarte mult, termenul Format:Math ajunge să domine, astfel încât toți ceilalți termeni pot fi neglijați, de exemplu, atunci când Format:Math, termenul Format:Math este de 1000 de ori mai mare ca termenul Format:Math. 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 Format:Math sau Format:Math. Chiar dacă Format:Math, dacă Format:Math, acesta din urmă îl va depăși întotdeauna pe primul când Format:Math crește mai mare decât 1.000.000 (Format:Math). Î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

$T(n)=O(n^2)$

fie

$T(n)\in O(n^2)$

și se spune că algoritmul are complexitate de ordinul lui Format:Math. 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 Format:Ill-wd.

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, Format:Ill-wd și două expresii ale acesteia care sunt valabile atunci când Format:Math este mic:

$\begin{array}{ccc}{e}^x& =1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots & \text{oricare ar fi }x\\ & =1+x+\frac{x^2}{2}+O(x^3)& \text{când }x\to 0\\ & =1+x+O(x^2)& \text{când }x\to 0\\ \end{array}$

Cea de a doua expresie (cea cu Format:Math) înseamnă că valoarea absolută a erorii Format:Math este de cel mult o constantă înmulțită cu Format:Math când Format:Math este suficient de aproape de 0.

Proprietăți

Dacă funcția Format:Math poate fi scrisă ca o sumă finită a altor funcții, atunci cea mai rapidă creștere determină ordinul lui Format:Math. De exemplu,

$f(n)=9\log n+5(\log n{)}^4+3n^2+2n^3=O(n^3)\text{când }n\to \mathrm{\infty }.$

În special, dacă o funcție poate fi legată de un polinom în Format:Math, atunci când Format:Math tinde spre infinit, se pot ignora termenii de grad mai mic ai polinomului. De asemenea, mulțimile Format:Math și Format:Math 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 Format:Math pentru oricare Format:Math se numește superpolinomială. Una care crește mai lent decât orice funcție exponențială de forma Format:Math 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 Format:Math.

Se poate ignora orice putere a lui Format:Math din interiorul logaritmilor. Mulțimea Format:Math este exact același cu Format:Math. Logaritmii diferă numai printr-un factor constant (întrucât Format:Math) ș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, Format:Math nu este același lucru cu Format:Math.

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 Format:Math, înlocuirea Format:Math cu Format:Math înseamnă că algoritmul rulează în timp de ordinul lui Format:Math, iar notația Big O ignoră constanta Format:Math. Aceasta se poate scrie ca Format:Math. Dacă, totuși, un algoritm rulează în timp de ordinul lui Format:Math, înlocuirea lui Format:Math cu Format:Math dă timp de ordinul Format:Math. Aceasta nu este echivalentă cu Format:Math în general. Schimbarea variabilelor poate afecta, de asemenea, ordinul algoritmului rezultat. De exemplu, dacă timpul de execuție al algoritmului este Format:Math atunci când este măsurat în termeni de număr Format:Math de cifre al unui număr de intrare Format:Math, timpul său de execuție este Format:Math ca funcție de numărul de intrare x însuși, deoarece Format:Math.

Produsul

$f_1=O(g_1)\text{ and }{f}_2=O(g_2)\Rightarrow f_1{f}_2=O(g_1{g}_2)$

$f\cdot O(g)=O(fg)$

Suma

$f_1=O(g_1)\text{ și }{f}_2=O(g_2)\Rightarrow f_1+f_2=O(max(g_1,g_2))$

Aceasta înseamnă că $f_1=O(g)\text{ și }{f}_2=O(g)\Rightarrow f_1+f_2\in O(g)$, ceea ce înseamnă că $O(g)$ este un con convex.

Înmulțirea cu o constantă

Fie Format:Math o constantă. Atunci:

$O(|k|g)=O(g)$ dacă Format:Math este nenul.

$f=O(g)\Rightarrow kf=O(g).$

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ă Format:Math și Format:Math sunt două funcții definite pe o anumită submulțime a lui ${ℝ}^n$. Se spune că

$f(\overrightarrow{x})\text{ este }O(g(\overrightarrow{x}))\text{ când }\overrightarrow{x}\to \mathrm{\infty }$

dacă și numai dacă

$\mathrm{\exists }M\mathrm{\exists }C>0\text{ astfel încât pentru orice }\overrightarrow{x}\text{ with }{x}_i\ge M\text{ pentru orice }i,|f(\overrightarrow{x})|\le C|g(\overrightarrow{x})|.$

În mod echivalent, condiția $x_i\ge M$ pentru unii $i$ poate fi înlocuită cu condiția $\Vert \overrightarrow{x}{\Vert }_{\mathrm{\infty }}\ge M$, unde cu $\Vert \overrightarrow{x}{\Vert }_{\mathrm{\infty }}$ se notează Format:Ill-wd. De exemplu, afirmația

$f(n,m)=n^2+m^3+O(n+m)\text{ când }n,m\to \mathrm{\infty }$

spune că există constantele Format:Math și Format:Math astfel încât

$\mathrm{\forall }\Vert (n,m){\Vert }_{\mathrm{\infty }}\ge M:|g(n,m)|\le C|n+m|,$

unde Format:Math se definește ca

$f(n,m)=n^2+m^3+g(n,m).$

Această definiție permite ca toate componentele lui $\overrightarrow{x}$ să crească până la infinit. În special, afirmația

$f(n,m)=O(n^m)\text{ când }n,m\to \mathrm{\infty }$

(de exemplu, $\mathrm{\exists }C\mathrm{\exists }M\mathrm{\forall }n\mathrm{\forall }m\dots$) este destul de diferită de

$\mathrm{\forall }m:f(n,m)=O(n^m)\text{ când }n\to \mathrm{\infty }$

(de exemplu, $\mathrm{\forall }m\mathrm{\exists }C\mathrm{\exists }M\mathrm{\forall }n\dots$).

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ă $f(n,m)=1$ și $g(n,m)=n$, atunci $f(n,m)=O(g(n,m))$ dacă se restrâng Format:Math și Format:Math la $[1,\mathrm{\infty }{)}^2$, dar nu dacă acestea sunt definite pe $[0,\mathrm{\infty }{)}^2$.

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 Format:Math este Format:Math, așa cum este definită mai sus, se scrie de obicei ca Format:Math. Unii consideră că acest lucru este un Format:Ill-wd, 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 Format:Ill-wd, este adevărat că Format:Math, dar nu și că Format:Math. 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 Format:Math din identitățile Format:Mathși Format:Math.”

Din aceste motive, ar fi mai precis să folosim Format:Ill-wd și să scriem Format:Math, considerând Format:Math ca clasă a tuturor funcțiilor Format:Math astfel încât Format:Math pentru o constantă Format:Math. 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.”

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 Format:Math se notează colecția de funcții având creșterea Format:Math plus o parte a cărei creștere este limitată la Format:Math. Prin urmare,

$g(x)=h(x)+O(f(x))$

exprimă același lucru ca și

$g(x)-h(x)=O(f(x)).$

Exemplu

Să presupunem că se dezvoltă un algoritm care să funcționeze pe o mulțime de Format:Math elemente. Dezvoltatorii săi sunt interesați să găsească o funcție Format:Math 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 Format:Math, iar după executarea subrutinei algoritmul trebuie să mai ruleze încă Format:Math pași înainte de a se termina. Astfel, complexitatea în timp a algoritmului poate fi exprimată ca Format:Math Aici termenii Format:Math sunt subsumați în cadrul lui Format:Math 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

În utilizarea mai complicată, O (...) poate să apară în diferite locuri într-o ecuație, chiar și de mai multe ori pe fiecare parte. De exemplu, următoarele sunt valabile pentru $n\to \mathrm{\infty }$:

$(n+1{)}^2=n^2+O(n)$

$(n+O(n^{1/2}))(n+O(\log n){)}^2=n^3+O(n^{5/2})$

$n^{O(1)}=O(e^n).$

Semnificația acestor afirmații este următoarea: pentru orice funcție care satisface fiecare Format:Math din partea stângă, există câteva funcții care satisfac fiecare Format:Math din partea dreaptă, astfel încât substituind toate aceste funcții, ecuația face ca cele două părți să fie egale. De exemplu, a treia ecuație de mai sus înseamnă: „Pentru orice funcție Format:Math, există o funcție Format:Math astfel încât Format:Math.” În ceea ce privește „notația mulțimilor” de mai sus, înțelesul este că clasa de funcții reprezentată de partea stângă este o submulțime a clasei de funcții reprezentate de partea dreaptă. În această utilizare, „=” este un simbol formal care, spre deosebire de utilizarea obișnuită a lui „=”, nu este o Format:Ill-wd. Astfel, de exemplu, Format:Math nu implică și afirmația falsă Format:Math

Scriere

Big O constă doar dintr-un „O” majuscul. Spre deosebire de notațiile cu nume grecești Bachmann-Landau, nu are nevoie de un simbol special. Cu toate acestea, variantele caligrafice frecvent utilizate, cum ar fi $𝒪$, sunt disponibile în sistemele LaTeX și în sisteme de fonturi derivate.

Ordinul de mărime al unor funcții comune

Mai jos sunt enumerate clase de funcții care se întâlnesc frecvent când se analizează timpul de funcționare al unui algoritm. În fiecare caz, Format:Math este o constantă pozitivă și Format:Math crește fără limitări. Funcțiile cu o creștere mai lentă sunt în general enumerate mai întâi.

Notație	Nume	Exemple
$O(1)$	constantă	Determinarea dacă un număr binar este par sau impar; Calculul lui $(-1{)}^n$; Utilizarea unei Format:Ill-wd de dimensiuni constante
$O(\log \log n)$	dublu logaritmică	Numărul de comparații folosit pentru a găsi un element folosind Format:Ill-wd într-un tabel sortat de valori uniform distribuite
$O(\log n)$	logaritmică	Găsirea unui element într-un tablou sortat cu căutare binară sau cu un Format:Ill-wd de căutare echilibrat, precum și toate operațiile pe un Format:Ill-wd
$O((\log n{)}^c)$ $c>1$	polilogaritmică	Ordonarea lanțurilor de matrice poate fi rezolvată în timp polilogaritmic pe o mașină cu acces aleator paralel.
$O(n^c)$ $0<c<1$	putere fracționară	Căutarea într-un Format:Ill-wd
$O(n)$	liniară	Găsirea unui element într-o listă neordonată sau într-un tablou neordonat; adunarea a doi întregi pe Format:Math biți prin sumatoare cu transport.
$O(n{\log }^{*}n)$	n Logaritm iterat n	Efectuarea de triangulări ale unui poligon simplu folosind algoritmul lui Seidel, sau algoritmul union–find. ${\log }^{*}(n)=\{\begin{array}{cc}0,& \text{if }n\le 1\\ 1+{\log }^{*}(\log n),& \text{if }n>1\end{array}$
$O(n\log n)=O(\log n!)$	linearitmică, logliniară, sau cvasiliniară	Efecturea unei Format:Ill-wd; Cea mai rapidă Format:Ill-wd; Format:Ill-wd and merge sort
$O(n^2)$	pătratică	Înmulțirea a două numere cu Format:Math cifre printr-un algoritm simplu; algoritmi de sortare simpli, cum ar fi Format:Ill-wd, Format:Ill-wd și Format:Ill-wd; limita (în cel mai rău caz) a unor algoritmi de regulă mai rapizi, ca quicksort, Format:Ill-wd, și Format:Ill-wd
$O(n^c)$	polinomială sau algebrică	Parsarea unor Format:Ill-wd; Format:Ill-wd maxim pentru grafuri bipartite; găsirea determinantului prin Format:Ill-wd
$L_n[\alpha ,c]=e^{(c+o(1))(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}$ $0<\alpha <1$	Format:Ill-wd sausubexponențială	Factorizarea unui număr folosind Format:Ill-wd sau Format:Ill-wd
$O(c^n)$ $c>1$	exponențtială	Găsirea soluției (exacte) a problemei comis-voiajorului folosind Format:Ill-wd; aflarea dacă două afirmații logice sunt echivalente folosind Format:Ill-wd
$O(n!)$	factorială	Rezolvarea problemei comis-voiajorului prin căutarea cu forță brută; generarea tuturor permutațiilor nerestricționate ale unei Format:Ill-wd; găsirea determinantului prin dezvoltare Laplace; enumerarea Format:Ill-wd

Afirmația $f(n)=O(n!)$ este uneori relaxată la $f(n)=O\left(n^n\right)$ pentru a obține formule mai simple pentru complexitatea asimptotică. Pentru orice Format:Math și Format:Math, $O(n^c(\log n{)}^k)$ este o submulțime a lui $O(n^{c+\epsilon })$ pentru orice $\epsilon >0$, deci poate fi considerat ca un polinom de grad mai mare.

Notații asimptotice asociate

Big O este cea mai frecvent folosită notație asimptotică pentru compararea funcțiilor. Împreună cu alte notații asociate, ea formează familia notațiilor Bachmann-Landau.

Notația Little-o

Intuitiv, afirmația „Format:Math este Format:Math” (a se citi Format:Math este little-o de Format:Math înseamnă că Format:Math crește mult mai rapid decât Format:Math. Fie Format:Math ca înainte o funcție cu valori reale sau complexe și Format:Math o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale numerelor reale pozitive, astfel încât Format:Math să fie strict pozitivă pentru toate valorile suficient de mari ale lui Format:Math. Se scrie

$f(x)=o(g(x))\text{ as }x\to \mathrm{\infty }$

dacă pentru orice constantă pozitivă Format:Math există o constantă Format:Math astfel încât

$|f(x)|\le \epsilon g(x)\text{ for all }x\ge N.$

De exemplu, avem

$2x=o(x^2)$ și $1/x=o(1).$

Diferența dintre definiția anterioară pentru notația big-O și definiția aceasta a lui little-o este că, în timp ce prima trebuie să fie adevărată pentru cel puțin o constantă Format:Math, aceasta din urmă trebuie să fie valabilă pentru orice constantă pozitivă Format:Math , oricât de mică ar fi. În acest fel, notația little-o face o afirmație mai puternică decât notația big-O corespunzătoare: orice funcție care este little-o a lui Format:Math este de asemenea big O al lui g, dar nu orice funcție care este big-O al lui Format:Math este și little-o de Format:Math. De exemplu, $2x^2=O(x^2)$ dar $2x^2\ne o(x^2).$

Deoarece Format:Math este nenul, sau cel puțin devine nenul dincolo de un anumit punct, relația Format:Math este echivalentă cu

$\underset{x\to \mathrm{\infty }}{\lim }\frac{f(x)}{g(x)}=0$ (și așa a definit, de fapt, Landau notația little-o).

Little-o respectă o serie de operații aritmetice. De exemplu,

dacă Format:Mvar este o constantă nenulă și $f=o(g)$ atunci $c\cdot f=o(g)$, și

dacă $f=o(F)$ și $g=o(G)$ atunci $f\cdot g=o(F\cdot G).$

De asemenea, ea satisface o relație de tranzitivitate:

dacă $f=o(g)$ și $g=o(h)$ atunci $f=o(h).$

Notația Big Omega

Există două definiții foarte răspândite și incompatibile ale afirmației

$f(x)=\mathrm{\Omega }(g(x))(x\to a),$

unde Format:Math este un număr real, ∞ sau -∞, unde Format:Math și Format:Math sunt funcții reale definite într-o vecinătate a lui Format:Math și unde Format:Math este pozitivă în această vecinătate.

Prima (cronologic) este folosită în teoria analitică a numerelor, iar cealaltă în teoria complexității. Când se întâlnesc cele două subiecte, această situație este generatoare de confuzie.

Definiția Hardy-Littlewood

În 1914, Format:Ill-wd și Format:Ill-wd au introdus noul simbol $\mathrm{\Omega }$, care este definit după cum urmează:

$f(x)=\mathrm{\Omega }(g(x))(x\to \mathrm{\infty })\iff \underset{x\to \mathrm{\infty }}{\mathrm{lim\; sup}}\left|\frac{f(x)}{g(x)}\right|>0.$

Prin urmare $f(x)=\mathrm{\Omega }(g(x))$ este negarea lui $f(x)=o(g(x))$.

În 1916, aceiași autori au introdus cele două noi simboluri ${\mathrm{\Omega }}_R$ și ${\mathrm{\Omega }}_L$, definite astfel:

$f(x)={\mathrm{\Omega }}_R(g(x))(x\to \mathrm{\infty })\iff \underset{x\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{f(x)}{g(x)}>0$;

$f(x)={\mathrm{\Omega }}_L(g(x))(x\to \mathrm{\infty })\iff \underset{x\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{f(x)}{g(x)}<0.$

Aceste simboluri au fost folosite de Format:Ill-wd, cu aceleași semnificații, în 1924. După Landau, notațiile nu au fost niciodată folosite din nou exact așa; ${\mathrm{\Omega }}_R$ a devenit ${\mathrm{\Omega }}_{+}$ și ${\mathrm{\Omega }}_L$ a devenit ${\mathrm{\Omega }}_{-}$.

Aceste trei simboluri $\mathrm{\Omega },{\mathrm{\Omega }}_{+},{\mathrm{\Omega }}_{-}$, precum și $f(x)={\mathrm{\Omega }}_{\pm }(g(x))$ (ceea ce înseamnă că sunt satisfăcute ambele relații$f(x)={\mathrm{\Omega }}_{+}(g(x))$ și $f(x)={\mathrm{\Omega }}_{-}(g(x))$), sunt acum utilizate în prezent în teoria analitică a numerelor.

Exemple simple

Avem

$\sin x=\mathrm{\Omega }(1)(x\to \mathrm{\infty }),$

și mai precis

$\sin x={\mathrm{\Omega }}_{\pm }(1)(x\to \mathrm{\infty }).$

Avem

$\sin x+1=\mathrm{\Omega }(1)(x\to \mathrm{\infty }),$

și mai precis

$\sin x+1={\mathrm{\Omega }}_{+}(1)(x\to \mathrm{\infty });$

dar

$\sin x+1={\mathrm{\Omega }}_{-}(1)(x\to \mathrm{\infty }).$

Definiția Knuth

În 1976, Donald Knuth a publicat o lucrare pentru a justifica utilizarea simbolului $\mathrm{\Omega }$ pentru a descrie o proprietate mai puternică. Knuth a scris: „Pentru toate aplicațiile pe care le-am văzut până acum în domeniul informaticii, o cerință mai puternică [...] este mult mai potrivită”. El a definit

$f(x)=\mathrm{\Omega }(g(x))\iff g(x)=O(f(x))$

cu comentariul: „Deși am schimbat definiția dată de Hardy și a Littlewood pentru $\mathrm{\Omega }$, mă simt justificat în acest sens, deoarece definiția lor nu este deloc folosită pe scară largă și pentru că există și alte modalități de a spune ceea ce vor ei să spună în cazurile relativ rare în care se aplică definiția lor.”

Familia de notații Bachmann-Landau

Notația	Nume	Descriere	Definiție formală	Limit Definition
$f(n)=o(g(n))$	Small O; Small Oh	Format:Mvar este dominată de Format:Mvar asimptotic	$\mathrm{\forall }k>0\mathrm{\exists }{n}_0\mathrm{\forall }n>n_0|f(n)|<k\cdot g(n)$	$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=0$
$f(n)=O(g(n))$	Big O; Big Oh; Big Omicron	$|f|$ este mărginită superior de Format:Mvar (până la un factor constant) asimptotic	$\mathrm{\exists }k>0\mathrm{\exists }{n}_0\mathrm{\forall }n>n_0|f(n)|\le k\cdot g(n)$	$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|f(n)|}{g(n)}<\mathrm{\infty }$
$f(n)=\mathrm{\Theta }(g(n))$	Big Theta	Format:Mvar este mărginită atât superior cât și inferior de Format:Mvar asimptotic	$\mathrm{\exists }{k}_1>0\mathrm{\exists }{k}_2>0\mathrm{\exists }{n}_0\mathrm{\forall }n>n_0$$k_1\cdot g(n)\le f(n)\le k_2\cdot g(n)$	$f(n)=O(g(n))$ și $f(n)=\mathrm{\Omega }(g(n))$ (versiunea Knuth)
$f(n)\sim g(n)$	De ordinul lui	Format:Mvar este egal cu Format:Mvar asimptotic	$\mathrm{\forall }\epsilon >0\mathrm{\exists }{n}_0\mathrm{\forall }n>n_0|\frac{f(n)}{g(n)}-1|<\epsilon$	$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=1$
$f(n)=\mathrm{\Omega }(g(n))$	Big Omega în teoria numerelor (Hardy–Littlewood)	$|f|$ nu este dominată de Format:Mvar asimptotic	$\mathrm{\exists }k>0\mathrm{\forall }{n}_0\mathrm{\exists }n>n_0|f(n)|\ge k\cdot g(n)$	$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\left|\frac{f(n)}{g(n)}\right|>0$
$f(n)=\mathrm{\Omega }(g(n))$	Big Omega în teoria complexității (Knuth)	Format:Mvar este mărginit inferior de Format:Mvar asimptotic	$\mathrm{\exists }k>0\mathrm{\exists }{n}_0\mathrm{\forall }n>n_{0}f(n)\ge k\cdot g(n)$	$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{f(n)}{g(n)}>0$
$f(n)=\omega (g(n))$	Small Omega	Format:Mvar domină Format:Mvar asimptotic	$\mathrm{\forall }k>0\mathrm{\exists }{n}_0\mathrm{\forall }n>n_0|f(n)|>k\cdot |g(n)|$	$\underset{n\to \mathrm{\infty }}{\lim }\left|\frac{f(n)}{g(n)}\right|=\mathrm{\infty }$

Definițiile limitelor presupun $g(n)\ne 0$ pentru Format:Mvar suficient de mare. Tabelul este (parțial) sortat de la cel mai mic la cel mai mare, în sensul că o, O, Θ, ~, Ω (versiunea lui Knuth), ω pe funcții corespund cu <, ≤, ≈, =, ≥, > pe dreapta reală (versiunea Hardy-Littlewood a lui Ω nu corespunde însă unei astfel de descrieri).

Informatica folosește Big O, big Theta Θ, little o, omega ω și notația Big Omega Ω a lui Knuth. Teoria analitică a numerelor utilizează adesea big O, small o, Big Omega Ω a lui Hardy-Littlewood (cu sau fără indicele +, - sau ±) și notațiile $\sim$. Notația small omega ω nu este utilizată la fel de des în analiză.

Utilizarea în informatică

În mod informal, în special în domeniul informaticii, notația big O poate fi folosită oarecum diferit pentru a descrie o legătură asimptotică strânsă acolo unde notația Theta Θ ar putea fi mai potrivită într-un anumit context. De exemplu, atunci când se analizează o funcție Format:Math, toate afirmațiile următoare sunt în general acceptabile, dar limite mai stricte (cum ar fi numerele 2 și 3 de mai jos) sunt de obicei preferate în locul limitelor mai relaxate (cum ar fi numărul 1 de mai jos).

1. Format:Math
2. Format:Math
3. Format:Math

Afirmațiile echivalente în română sunt:

1. Format:Math crește asymptotic nu mai repede decât Format:Math
2. Format:Math crește asymptotic nu mai repede decât Format:Math
3. Format:Math crește asimptotic la fel de repede ca Format:Math.

Deci, în timp ce toate cele trei afirmații sunt adevărate, în fiecare din ele există progresiv mai multe informații. În unele domenii, cu toate acestea, notația Big O (numărul 2 din listele de mai sus) ar fi folosită mai frecvent decât notația Big Theta (punctele 3 din listele de mai sus). De exemplu, dacă Format:Math reprezintă timpul de funcționare a algoritmului nou dezvoltat pentru dimensiunea de intrare Format:Math, inventatorii și utilizatorii algoritmului ar putea fi mai înclinați să pună o limită asimptotică superioară timpului cât va dura funcționarea lui, fără a face vreo afirmație explicită despre limita inferioară asimptotică.

Alte notații

În cartea lor Format:Ill-wd, Format:Ill-wd, Format:Ill-wd, Rivest și Format:Ill-wd iau în considerare mulțimea funcțiilor Format:Math care satisfac

$f(n)=O(g(n))(n\to \mathrm{\infty }).$

Într-o notație corectă, această mulțime poate fi, de exemplu, numită Format:Math, unde

$O(g)=\{f:$ există constante pozitive Format:Math și $n_0$ astfel încât $0\le f(n)\le cg(n)$ pentru toți $n\ge n_0\}$.

Autorii afirmă că folosirea operatorului de egalitate (=) pentru a nota apartenența la mulțime, în locul operatorului de apartenență încetățenit (∈), este un abuz de notație, dar acest lucru are avantaje. Într-o ecuație sau inegalitate, folosirea unei notații asimptotice reprezintă o funcție anonimă din mulțimea Format:Math, care elimină termenii de ordin inferior și ajută la reducerea aglomerării inutile în ecuații, de exemplu:

$2n^2+3n+1=2n^2+O(n).$

Extensii la notațiile Bachmann-Landau

O altă notație folosită uneori în domeniul informaticii este Õ (citiți soft-O): Format:Math este o prescurtare pentru Format:Math pentru un anume Format:Math. În esență, este o notație Big O, ignorând factorii logaritmici, deoarece efectele ratei de creștere a unei alte funcții superlogaritmice indică o explozie a ratei de creștere pentru parametrii de intrare de dimensiuni mari, care este mai importantă pentru a prezice relele performanțe efectele mai fine cu care contribuie de factorul (factorii) de creștere logaritmică. Această notație este adesea folosită pentru a evita „pierderea în amănunte” în cadrul vitezelor de creștere care sunt declarate ca fiind prea strâns mărginite pentru chestiunea relevantă (întrucât Format:Math este întotdeauna Format:Math pentru orice constantă Format:Math și orice Format:Math).

De asemenea, Format:Ill-wd, definită ca

$L_n[\alpha ,c]=e^{(c+o(1))(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}$

este convenabilă pentru funcțiile care sunt între polinomială și exponențială în raport cu $\ln n$.

Generalizări și utilizări conexe

Generalizarea funcțiilor care iau valori în orice spațiu vectorial normat este simplă (înlocuind valoarea absolută cu norma), unde Format:Math și Format:Math nu este nevoie săi aibă valori în același spațiu. O generalizare a funcțiilor Format:Math cu valori în orice Format:Ill-wd este de asemenea posibilă. „Procesul de limitare” Format:Math poate fi și el generalizat prin introducerea unei Format:Ill-wd arbitrare, adică a Format:Ill-wd direcționate Format:Math și Format:Math. Notația Format:Math poate fi folosită pentru a defini derivate și diferențiabilitatea în spații destul de generale, precum și echivalența (asimptotică) a funcțiilor,

$f\sim g⟺(f-g)\in o(g)$

care este o relație de echivalență și o noțiune mai restrictivă decât relația „Format:Math este Format:Math” de mai sus. (Se reduce la Format:Math dacă Format:Math și Format:Math sunt funcții cu valoare reală pozitivă.) De exemplu, Format:Math este Format:Math, dar Format:Math nu este Format:Math.

Istorie (notații Bachmann-Landau, Hardy și Vinogradov)

Simbolul O a fost introdus pentru prima dată de teoreticianul numerelor Paul Bachmann în 1894, în al doilea volum al cărții sale Format:Lang („Teoria analitică a numerelor”), al cărei prim volum (care nu conținea încă notația Big O) a fost publicat în 1892. Teoreticianul numerelor Format:Ill-wd a adoptat-o și, astfel, a fost inspirat să introducă în 1909 notația o; aici ambele sunt numite acum simboluri Landau. Aceste notații au fost folosite în matematica aplicată în anii 1950 pentru analiza asimptotică. Simbolul $\mathrm{\Omega }$ (în sensul „nu este Format:Math de”) a fost introdus în 1914 de Hardy și Littlewood. Hardy și Littlewood au introdus, de asemenea, în 1918 simbolurile ${\mathrm{\Omega }}_R$ („dreapta”) și ${\mathrm{\Omega }}_L$ („stânga”), precursori ai simbolurilor moderne ${\mathrm{\Omega }}_{+}$ („nu este mai mică decât small Format:Math de”) și ${\mathrm{\Omega }}_{-}$ („nu este mai mare decât small Format:Math de”). Astfel, simbolurile Omega (cu semnificațiile lor originale) sunt uneori denumite și „simboluri Landau”. Această notație $\mathrm{\Omega }$ a devenit frecvent folosită în teoria numerelor cel puțin din anii 1950. În anii 1970, Big O a fost popularizată în domeniul informaticii de către Donald Knuth, care a introdus notația aferentă Theta și a propus o altă definiție pentru notația Omega.

Landau nu a folosit niciodată Theta mare și simboluri omega-mic.

Simbolurile lui Hardy erau (din punct de vedere al notației O moderne)

$f\preccurlyeq g⟺f\in O(g)$   and   $f\prec g⟺f\in o(g);$

(Hardy însă nu a definit niciodată și nu a folosit notația $\prec \prec$, nici $\ll$, așa cum s-a afirmat uneori). De asemenea, Hardy a introdus simbolurile $\preccurlyeq$ și $\prec$ (precum și alte simboluri) în tratatul său din 1910, „Orders of Infinity”, și îl folosește doar în trei lucrări (1910-1913). În restul de aproape 400 de lucrări și cărți, el folosește consistent simbolurile Landau O și o.

Notația lui Hardy nu mai este folosită. Pe de altă parte, în 1930, teoreticianului rus al numerelor Format:Ill-wd a introdus notația lui, $\ll$, care este folosită din ce în ce mai mult în teoria numerelor în locul notației $O$. Avem

$f\ll g⟺f\in O(g),$

și în mod obișnuit ambele notații sunt utilizate în aceeași lucrare.

Big O reprezenta inițial „de ordinul lui” ("Ordnung", Bachmann 1894) și este așadar o literă latină. Nici Bachmann, nici Landau nu o numesc vreodată „Omicron”. Simbolul a fost considerat mult mai târziu (1976) de către Knuth drept omicron mare probabil în legătură cu definiția sa a simbolului Omega. Nu se folosește cifra zero.

Lectură suplimentară

• Format:Citat carte
• Format:Citat carte
• Format:Citat carte
• Format:Citat carte
• Format:Cite conference
• Format:Citat web
• Format:Citat web
• Format:Citat web
• Format:Citat web
• Format:Citat web

Legături externe

• Creșterea șirurilor - OEIS (Online Encyclopedia of Integer Sequences) Wiki
• Introducere în notații asimptoticeFormat:Legătură nefuncțională
• Simboluri Landau
• Notația Big-O - la ce servește
• Big O Notation explicată în engleză simplă