bool findElement(int arr[], int n, int key) {  for (int i = 0; i < n; i++) {  if (arr[i] == key) {  return true;  }  }  return false; }>

int binarySearch(int arr[], int l, int r, int x) {  if (r>= l) { int mid = l + (r - l) / 2;  if (arr[mid] == x) return mid;  if (arr[mid]> x) returnează binarySearch(arr, l, mid - 1, x);  return binarySearch(arr, mid + 1, r, x);  } returnează -1; }>>> 
3. Complexitatea timpului cuadratic: O mare (n2) Complexitate
Complexitatea timpului patratic înseamnă că timpul de rulare al unui algoritm este proporțional cu pătratul mărimii intrării.
 
De exemplu, un simplu  algoritm de sortare cu bule  are o complexitate de timp pătratică:
Fragment de codComplexitatea timpului cubic înseamnă că timpul de rulare al unui algoritm este proporțional cu cubul mărimii intrării.
 
De exemplu, un naiv algoritm de multiplicare a matricei are o complexitate în timp cub:
Fragment de codComplexitatea timpului polinomial se referă la complexitatea timpului a unui algoritm care poate fi exprimat ca o funcție polinomială a mărimii de intrare    n    . În Big    O    notație, se spune că un algoritm are complexitate în timp polinomială dacă complexitatea sa în timp este    Pe       k       )    , Unde    k    este o constantă și reprezintă gradul polinomului.
 
Algoritmii cu complexitate în timp polinomial sunt în general considerați eficienți, deoarece timpul de rulare crește cu o rată rezonabilă pe măsură ce dimensiunea intrării crește. Exemple comune de algoritmi cu complexitate în timp polinomial includ    complexitate liniară în timp O(n)    ,    complexitate de timp pătratică O(n       2       )    , și    complexitatea timpului cubic O(n       3       )    .
 
6. Complexitatea timpului exponențial: O mare (2n) Complexitate
Complexitatea timpului exponențial înseamnă că timpul de rulare al unui algoritm se dublează cu fiecare adăugare la setul de date de intrare.
concat șiruri de caractere java
 
De exemplu, problema lui generând toate submulțimile unei mulțimi este de complexitate exponențială în timp:
Fragment de cod 
void generateSubsets(int arr[], int n) {  for (int i = 0; i < (1 << n); i++) {  for (int j = 0; j < n; j++) {  if (i & (1 << j)) {  cout << arr[j] << ' ';  }  }  cout << endl;  } }>
  
Complexitate factorială de timp: complexitate mare O(n!).
Complexitatea factorială a timpului înseamnă că timpul de rulare al unui algoritm crește factorial odată cu dimensiunea intrării. Acest lucru este adesea văzut în algoritmii care generează toate permutările unui set de date.
 
Iată un exemplu de algoritm de complexitate a timpului factorial, care generează toate permutările unui tablou:
Fragment de cod 
void permute(int* a, int l, int r) {  if (l == r) {  for (int i = 0; i <= r; i++) {  cout << a[i] << ' ';  }  cout << endl;  }  else {  for (int i = l; i <= r; i++) {  swap(a[l], a[i]);  permute(a, l + 1, r);  swap(a[l], a[i]); // backtrack  }  } }>
  
Dacă tragem cele mai comune exemple de notație Big O, am avea un grafic ca acesta:
 
 
 
Cum se determină notația Big O?
    Notație O mare    este o notație matematică folosită pentru a descrie    comportament asimptotic    a unei funcții pe măsură ce intrarea acesteia crește infinit de mare. Acesta oferă o modalitate de a caracteriza eficiența algoritmilor și a structurilor de date.
 
Pași pentru a determina notația Big O:
    1. Identificați termenul dominant:    
 
Examinați funcția și identificați termenul cu cel mai mare ordin de creștere pe măsură ce dimensiunea intrării crește.
Ignorați factorii constanți sau termenii de ordin inferior.
    2. Determinați ordinea de creștere:    
 
Ordinea de creștere a termenului dominant determină notația Big O.
    3. Scrieți notația O mare:    
 
Notația Big O este scrisă ca O(f(n)), unde f(n) reprezintă termenul dominant.
De exemplu, dacă termenul dominant este n^2, notația Big O ar fi O(n^2).
    4. Simplificați notația (Opțional):    
 
În unele cazuri,    Brandul Big O    n poate fi simplificat prin eliminarea factorilor constanți sau prin utilizarea unei notații mai concise.
De exemplu,    O(2n)    poate fi simplificat la    Pe).    
    Exemplu:    
bara de instrumente cu acces rapid Word
  
Funcția: f(n) = 3n3+ 2n2+ 5n + 1
 
Termen dominant: 3n3
Ordine de creștere: cubic (n3)
Notație O mare: O(n3)
Notație simplificată: O(n3)
    Exemple matematice de analiză în timp de rulare:    
Tabelul de mai jos ilustrează analiza timpului de rulare a diferitelor ordine de algoritmi pe măsură ce mărimea intrării (n) crește.
 
n
jurnal(n)
n
n * log(n)
n^2
2^n
n!
10
1
10
10
100
1024
3628800
douăzeci
2.996
douăzeci
59,9
400
1048576
2.432902e+1818
    Exemple algoritmice de analiză a timpului de rulare:    
Tabelul de mai jos clasifică algoritmii în funcție de complexitatea lor de rulare și oferă exemple pentru fiecare tip.
 
Tip
Notaţie
Exemple de algoritmi
Logaritmic
O(log n)
Căutare binară
Liniar
Pe)
Căutare liniară
Superliniar
O(n log n)
Sortare în grămada, Sortare îmbinare
Polinom
O(n^c)
Înmulțirea matricei lui Strassen, sortarea cu bule, sortarea selecției, sortarea inserției, sortarea găleții
Exponenţial
O(c^n)
Turnul din Hanoi
Factorială
Pe!)
Expansiunea determinantă de către minori, algoritmul de căutare cu forță brută pentru problema vânzătorului ambulant
Clase de algoritm cu număr de operații și timp de execuție:
Mai jos sunt clasele de algoritmi și timpii lor de execuție pe un computer care se execută    1 milion de operații pe secundă (1 sec = 10       6       μsec = 10       3       msec)    :
 
Clasele de notație Big O
 
f(n)
 
Analiza Big O (număr de operații) pentru n = 10
 
Timp de execuție (1 instrucțiune/μsec)
constant
 
O(1)
 
1
 
1 μsec
 
logaritmică
 
O(logn)
 
3.32
 
3 μsec
 
liniar
 
Pe)
 
10
 
10 μsec
 
O(nlogn)
 
O(nlogn)
 
33.2
 
33 μsec
 
pătratică
 
Pe2)
 
102
 
100 μsec
 
cub
 
Pe3)
 
103
 
1 msec
 
exponenţială
 
O(2n)
 
1024
 
10 msec
 
factorial
 
Pe!)
 
10!
 
3,6288 sec
 
Comparație între notația Big O, Big Ω (Omega) și Big θ (Theta):
Mai jos este un tabel care compară notația Big O, notația Ω (Omega) și notația θ (Theta):
npm cache curat
 
Notaţie
Definiție
Explicaţie
O mare (O)
f(n) ≤ C * g(n) pentru toate n ≥ n0
Descrie limita superioară a timpului de rulare a algoritmului în    cel mai rău caz    .
Ω (Omega)
f(n) ≥ C * g(n) pentru toate n ≥ n0
Descrie limita inferioară a timpului de rulare a algoritmului în    cel mai bun caz    .
θ (Theta)
C1* g(n) ≤ f(n) ≤ C2* g(n) pentru n ≥ n0
Descrie atât limitele superioare, cât și inferioare ale algoritmului    timpul pentru alergat    .
În fiecare notație:
 
    f(n)    reprezintă funcția analizată, de obicei complexitatea temporală a algoritmului.
    g(n)    reprezintă o funcție specifică care limitează    f(n)    .
    C, C1,    și    C2    sunt constante.
    n       0    este dimensiunea minimă a intrării dincolo de care este valabilă inegalitatea.
Aceste notații sunt folosite pentru a analiza algoritmi pe baza lor    cel mai rău caz (O mare)    ,    cel mai bun caz (Ω)    , și    caz mediu (θ)    scenarii.
 
Întrebări frecvente despre Big O Notation:
Întrebarea 1. Ce este Big O Notation?
 
    Răspuns:    Big O Notation este o notație matematică folosită pentru a descrie limita superioară a complexității timpului unui algoritm în ceea ce privește modul în care crește în raport cu dimensiunea intrării.
 
Întrebarea 2. De ce este importantă notația Big O?
 
    Răspuns:    Ne ajută să analizăm și să comparăm eficiența algoritmilor, concentrându-ne pe cel mai rău scenariu și înțelegerea modului în care performanța lor se scalează în funcție de dimensiunea intrării.
 
Întrebarea 3. Cum se calculează Big O Notation?
 
    Răspuns:    Notația Big O este determinată prin identificarea operației dominante într-un algoritm și exprimând complexitatea sa de timp în termeni de n, unde n reprezintă dimensiunea intrării.
 
Întrebarea 4. Ce înseamnă O(1) în notația Big O?
 
    Răspuns:    O(1) semnifică o complexitate constantă în timp, indicând faptul că timpul de execuție al unui algoritm nu se modifică indiferent de dimensiunea intrării.
 
Întrebarea 5. Care este semnificația diferitelor complexități Big O precum O(log n) sau O(n^2)?
 
    Răspuns:    Diferitele complexități precum O(log n) sau O(n^2) reprezintă modul în care performanța unui algoritm crește pe măsură ce dimensiunea intrării crește, oferind informații despre eficiența și scalabilitatea acestuia.
 
Întrebarea 6. Notația Big O poate fi aplicată și complexității spațiului?
 
    Răspuns:    Da, Big O Notation poate fi folosită și pentru a analiza și a descrie complexitatea spațiului unui algoritm, indicând câtă memorie are nevoie în raport cu dimensiunea de intrare.
 
    Articol înrudit:    
 Exemple de analiză Big-O 
 Proiectarea și analiza algoritmilor 
 Tipuri de notații asimptotice în analiza complexității algoritmilor 
  Analiza algoritmilor | Big – Ω (Big- Omega) Notație  
 Analiza algoritmilor | mici o și mici notații omega