Notația Big O | o modalitate de a compara ratele de creștere a diferitelor funcții

În matematică și informatică, notația Big O este o modalitate de a compara ratele de creștere a diferitelor funcții. Este adesea utilizată pentru a compara eficiența diferiților algoritmi, ceea ce se face prin calcularea cantității de memorie necesară și a timpului necesar pentru a finaliza.

Notația Big O este adesea utilizată pentru a identifica gradul de complexitate al unei probleme, cunoscută și sub numele de clasa de complexitate a problemei. Matematicianul Paul Bachmann (1837-1920) a fost primul care a folosit această notație, în cea de-a doua ediție a cărții sale "Analytische Zahlentheorie", în 1896. Edmund Landau (1877-1938) a popularizat notația. Din acest motiv, atunci când se vorbește despre simbolurile Landau, se face referire la această notație.

Notația Big O este denumită astfel după termenul "ordinul funcției", care se referă la creșterea funcțiilor. Notația Big O este utilizată pentru a găsi limita superioară (cea mai mare valoare posibilă) a ratei de creștere a funcției, ceea ce înseamnă că se calculează cel mai lung timp necesar pentru a transforma intrarea în ieșire. Acest lucru înseamnă că un algoritm poate fi grupat în funcție de timpul pe care îl poate dura în cel mai rău caz, în care se va urma de fiecare dată calea cea mai lungă.

Mai precis, date două funcții pozitive f ( x ) {\displaystyle f(x)} f(x) și g ( x ) {\displaystyle g(x)} $g(x)$ , spunem că f {\displaystyle f} se află în O mare a lui g {\displaystyle g} (scris f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ) dacă pentru un număr suficient de mare de x {\displaystyle x} , f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ pentru o anumită constantă k {\displaystyle k} .

Big O este o expresie care găsește timpul de execuție în cel mai pesimist scenariu, arătând cât de eficient este un algoritm fără a fi nevoie să se ruleze programul pe un computer. Acest lucru este util și datorită faptului că diferite computere pot avea hardware diferit și, prin urmare, au nevoie de diferite cantități de timp pentru a-l finaliza. Deoarece Big O presupune întotdeauna cel mai rău caz, poate arăta o măsurătoare coerentă a vitezei: indiferent de hardware, O ( 1 ) {\displaystyle O(1)} $O(1)$ se va finaliza întotdeauna mai repede decât O ( n ! ) {\displaystyle O(n!)}. $O(n!)$ , deoarece acestea au niveluri diferite de eficiență.

Exemple

Exemplele următoare folosesc toate coduri scrise în Python. Rețineți că aceasta nu este o listă completă a tipurilor Big O.

Constant

O ( 1 ) {\displaystyle O(1)} $O(1)$ durează întotdeauna același timp, indiferent de datele de intrare. De exemplu, să luăm o funcție care acceptă un număr întreg (numit x) și returnează dublul valorii sale:

def double(x): return x * 2 #Returnează valoarea lui x înmulțit cu 2

După acceptarea intrării, această funcție va face întotdeauna un pas pentru a returna o ieșire. Este constantă, deoarece va dura întotdeauna același timp, deci este O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linear

O ( n ) {\displaystyle O(n)} $O(n)$ crește în funcție de mărimea intrării, reprezentată de n {\displaystyle n} . De exemplu, pentru următoarea funcție care acceptă n și returnează fiecare număr de la 1 la n:

def count(n): i = 1 #Crearea unui contor numit "i" cu valoarea 1 while i <= n: #În timp ce i este mai mic sau egal cu n print(i) #Imprimă valoarea lui i = i + 1 #Redefinește i ca "valoarea lui i + 1"

Dacă am introduce valoarea 5, atunci ar ieși $1,2,3,4,5$ , necesitând 5 bucle pentru a se finaliza. În mod similar, dacă introducem valoarea 100, atunci ar ieși $1,2,3...98,99,100$ , ceea ce ar necesita 100 de bucle pentru a se finaliza. Dacă intrarea este n {\displaystyle n}. , atunci timpul de execuție al algoritmului este exact n {\displaystyle n} bucle de fiecare dată, deci este O ( n ) {\displaystyle O(n)} . $O(n)$

Factorial

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ crește în cantități factoriale, ceea ce înseamnă că timpul necesar crește masiv odată cu numărul de date de intrare. De exemplu, să presupunem că dorim să vizităm cinci orașe din întreaga lume și că dorim să vedem fiecare ordine posibilă (permutare). Un algoritm pe care l-am putea scrie folosind biblioteca itertools din Python este următorul:

import itertools #Importă biblioteca itertools cities = ['Londra', 'Paris', 'Berlin', 'Amsterdam', 'Roma'] #Un tablou cu orașele alese def permutations(cities): #Consumularea unei matrice de orașe ca intrare: for i in itertools.permutations(cities): #Pentru fiecare permutare a elementelor noastre (atribuite variabilei "i") print(i) #Scoaterea i

Acest algoritm va calcula fiecare permutare unică a orașelor noastre și apoi o va afișa. Exemple de rezultate vor include:

("Londra", "Paris", "Berlin", "Amsterdam", "Roma") ("Londra", "Paris", "Berlin", "Roma", "Amsterdam") ("Londra", "Paris", "Amsterdam", "Berlin", "Roma") ... ("Roma", "Amsterdam", "Paris", "Berlin", "Londra") ("Roma", "Amsterdam", "Berlin", "Londra") ("Roma", "Amsterdam", "Berlin", "Londra", "Paris") ("Roma", "Amsterdam", "Berlin", "Paris", "Londra")

Aici, lista noastră de intrări are 5 elemente, iar pentru fiecare selecție, opțiunile rămase scad cu 1. Cu alte cuvinte, cele 5 intrări aleg $5\times 4\times 3\times 2\times 1$ elemente (sau 5 ! {\displaystyle 5!} $5!$ ). Dacă intrarea noastră are o lungime de n {\displaystyle n} orașe, atunci numărul de ieșiri este n ! {\displaystyle n!} $n!$ ; în general, presupunând că trecem prin fiecare permutare, vom avea nevoie de O ( n ! ) {\displaystyle O(n!)} $O(n!)$ bucle pentru a o finaliza.

Notația Little-o

Un concept înrudit cu notația big-O este notația little-o. Big-O este folosită pentru a spune că o funcție nu crește mai repede decât o altă funcție, în timp ce little-o este folosită pentru a spune că o funcție crește mai încet decât o altă funcție. În cazul în care două funcții cresc în același ritm, se poate folosi notarea big-O, dar nu și little-o. Diferența dintre big-O și little-o este similară cu diferența dintre ≤ {\displaystyle \leq } $\leq$ și < {\displaystyle <} $<$ .

Dacă f ( x ) {\displaystyle f(x)} crește mai lent decât g ( x ) {\displaystyle g(x)} $g(x)$ , atunci $f(x)\in O(g(x))$ și $f(x)\in o(g(x))$ .
Dacă f ( x ) {\displaystyle f(x)} crește cu aceeași rată ca și g ( x ) {\displaystyle g(x)} $g(x)$ , atunci $f(x)\in O(g(x))$ dar f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Dacă f ( x ) {\displaystyle f(x)} crește cu o viteză mai mare decât g ( x ) {\displaystyle g(x)} $g(x)$ , atunci f ( x ) ∉ $f(x)\not \in O(g(x))$ și f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Întrebări și răspunsuri

Î: Ce este notația Big O?

R: Notația Big O este o modalitate de a compara ratele de creștere a diferitelor funcții, adesea utilizată pentru a compara eficiența diferiților algoritmi prin calcularea cantității de memorie și a timpului necesar pentru a finaliza. De asemenea, poate fi utilizată pentru a identifica cât de complexă este o problemă.

Î: Cine a fost primul care a folosit această notație?

R: Matematicianul Paul Bachmann (1837-1920) a fost primul care a folosit această notație în cartea sa "Analytische Zahlentheorie" din 1896.

Î: Ce înseamnă Big O?

R: Big O înseamnă "ordinul funcției", care se referă la rata de creștere a funcțiilor.

Î: Cum se utilizează Big O?

R: Notația Big O este utilizată pentru a găsi o limită superioară (cea mai mare valoare posibilă) a ratei de creștere a funcției, ceea ce înseamnă că se calculează cel mai lung timp necesar pentru a transforma o intrare în ieșire. Acest lucru înseamnă că algoritmii pot fi grupați în funcție de timpul pe care îl necesită în cel mai rău caz, în care se va alege de fiecare dată calea cea mai lungă.

Î: Ce sunt simbolurile Landau?

R: Simbolurile Landau se referă la notația Big O, numită după Edmund Landau (1877-1938), care a făcut populară această notație.

Î: De ce este util Big O?

R: Big O ne permite să măsurăm viteza fără a fi nevoie să rulăm programe pe computere, deoarece presupune întotdeauna cele mai rele scenarii, ceea ce o face coerentă indiferent de diferențele hardware dintre computere. De asemenea, arată cât de eficient este un algoritm fără a fi nevoie să îl rulăm efectiv pe un computer.