logo

TechCodeview

Tutoriel de notation Big O – Un guide de l'analyse Big O

Notation grand O est un outil puissant utilisé en informatique pour décrire la complexité temporelle ou spatiale des algorithmes. Il fournit un moyen standardisé de comparer l’efficacité de différents algorithmes en termes de performances dans le pire des cas. Compréhension Notation grand O est essentiel pour analyser et concevoir des algorithmes efficaces.

Dans ce tutoriel, nous aborderons les bases de Notation grand O , sa signification et comment analyser la complexité des algorithmes à l'aide Grand O .



Table des matières

Qu'est-ce que la notation Big-O ?

Big-O , communément appelé Ordre de , est une façon d'exprimer le limite supérieure de la complexité temporelle d’un algorithme, puisqu’il analyse pire cas situation de l'algorithme. Il fournit un limite supérieure sur le temps pris par un algorithme en termes de taille de l'entrée. C’est noté comme O(f(n)) , où f(n) est une fonction qui représente le nombre d'opérations (étapes) qu'un algorithme effectue pour résoudre un problème de taille n .



Notation Big-O est utilisé pour décrire les performances ou la complexité d’un algorithme. Plus précisément, il décrit le pire scénario en termes de temps ou complexité spatiale.

Point important:

  • Notation grand O décrit uniquement le comportement asymptotique d'une fonction, pas sa valeur exacte.
  • Le Notation grand O peut être utilisé pour comparer l’efficacité de différents algorithmes ou structures de données.

Définition de la notation Big-O :

Étant donné deux fonctions f(n) et g(n) , nous disons que f(n) est O(g(n)) s'il existe des constantes c> 0 et n 0 >= 0 tel que f(n) <= c*g(n) pour tous n>= n 0 .



En termes plus simples, f(n) est O(g(n)) si f(n) ne pousse pas plus vite que c*g(n) pour tout n>= n0où c et n0sont des constantes.

survoler en CSS

Pourquoi la notation Big O est-elle importante ?

La notation Big O est une notation mathématique utilisée pour décrire la pire complexité temporelle ou l'efficacité d'un algorithme ou la pire complexité spatiale d'une structure de données. Il fournit un moyen de comparer les performances de différents algorithmes et structures de données, et de prédire comment ils se comporteront à mesure que la taille d'entrée augmente.

La notation Big O est importante pour plusieurs raisons :

  • La notation Big O est importante car elle permet d'analyser l'efficacité des algorithmes.
  • Il fournit un moyen de décrire comment le Durée ou besoins en espace d'un algorithme augmente à mesure que la taille d'entrée augmente.
  • Permet aux programmeurs de comparer différents algorithmes et de choisir le plus efficace pour un problème spécifique.
  • Aide à comprendre l’évolutivité des algorithmes et à prédire leurs performances à mesure que la taille d’entrée augmente.
  • Permet aux développeurs d'optimiser le code et d'améliorer les performances globales.

Propriétés de la notation Big O :

Vous trouverez ci-dessous quelques propriétés importantes de la notation Big O :

1. Réflexivité :

Pour toute fonction f(n), f(n) = O(f(n)).

Exemple:

f(n) = n2, alors f(n) = O(n2).

2. Transitivité :

Si f(n) = O(g(n)) et g(n) = O(h(n)), alors f(n) = O(h(n)).

Exemple:

f(n) = n3, g(n) = n2, h(n) = n4. Alors f(n) = O(g(n)) et g(n) = O(h(n)). Par conséquent, f(n) = O(h(n)).

3. Facteur constant :

Pour toute constante c> 0 et fonctions f(n) et g(n), si f(n) = O(g(n)), alors cf(n) = O(g(n)).

Exemple:

f(n) = n, g(n) = n2. Alors f(n) = O(g(n)). Par conséquent, 2f(n) = O(g(n)).

4. Règle de somme :

Si f(n) = O(g(n)) et h(n) = O(g(n)), alors f(n) + h(n) = O(g(n)).

Exemple:

f(n) = n2, g(n) = n3, h(n) = n4. Alors f(n) = O(g(n)) et h(n) = O(g(n)). Par conséquent, f(n) + h(n) = O(g(n)).

5. Règle du produit :

Si f(n) = O(g(n)) et h(n) = O(k(n)), alors f(n) * h(n) = O(g(n) * k(n)) .

Exemple:

f(n) = n, g(n) = n2, h(n) = n3, k(n) = n4. Alors f(n) = O(g(n)) et h(n) = O(k(n)). Par conséquent, f(n) * h(n) = O(g(n) * k(n)) = O(n5).

6. Règle de composition :

Si f(n) = O(g(n)) et g(n) = O(h(n)), alors f(g(n)) = O(h(n)).

Exemple:

f(n) = n2, g(n) = n, h(n) = n3. Alors f(n) = O(g(n)) et g(n) = O(h(n)). Par conséquent, f(g(n)) = O(h(n)) = O(n3).

Notations courantes Big-O :

La notation Big-O est un moyen de mesurer la complexité temporelle et spatiale d'un algorithme. Il décrit la limite supérieure de la complexité dans le pire des cas. Examinons les différents types de complexités temporelles :

1. Complexité temporelle linéaire : complexité Big O(n)

La complexité temporelle linéaire signifie que le temps d'exécution d'un algorithme augmente linéairement avec la taille de l'entrée.

table de vérité de l'additionneur complet

Par exemple, considérons un algorithme qui parcourt un tableau pour trouver un élément spécifique :

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

2. Complexité temporelle logarithmique : complexité Big O (log n)

La complexité temporelle logarithmique signifie que le temps d'exécution d'un algorithme est proportionnel au logarithme de la taille d'entrée.

Par exemple, un algorithme de recherche binaire a une complexité temporelle logarithmique :

Extrait de code 
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) return binaireSearch(arr, l, mid - 1, x);  return binaireSearch(arr, mid + 1, r, x);  } renvoie -1 ; }>

3. Complexité temporelle quadratique : Grand O(n2) Complexité

La complexité temporelle quadratique signifie que le temps d'exécution d'un algorithme est proportionnel au carré de la taille d'entrée.

Par exemple, un simple algorithme de tri à bulles a une complexité temporelle quadratique :

Extrait de code 
void bubbleSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {  for (int j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]);  } } } }>

4. Complexité du temps cubique : Grand O(n3) Complexité

La complexité temporelle cubique signifie que le temps d'exécution d'un algorithme est proportionnel au cube de la taille d'entrée.

Par exemple, un naïf algorithme de multiplication matricielle a une complexité temporelle cubique :

Extrait de code 
void multiply(int mat1[][N], int mat2[][N], int res[][N]) {  for (int i = 0; i < N; i++) {  for (int j = 0; j < N; j++) {  res[i][j] = 0;  for (int k = 0; k < N; k++)  res[i][j] += mat1[i][k] * mat2[k][j];  }  } }>

5. Complexité temporelle polynomiale : Grand O(nk) Complexité

La complexité temporelle polynomiale fait référence à la complexité temporelle d'un algorithme qui peut être exprimée comme une fonction polynomiale de la taille d'entrée. n . En grand Ô notation, un algorithme est dit avoir une complexité temporelle polynomiale si sa complexité temporelle est Sur k ) , où k est une constante et représente le degré du polynôme.

Les algorithmes avec une complexité temporelle polynomiale sont généralement considérés comme efficaces, car le temps d'exécution augmente à un rythme raisonnable à mesure que la taille de l'entrée augmente. Des exemples courants d'algorithmes avec une complexité temporelle polynomiale incluent complexité temporelle linéaire O(n) , complexité temporelle quadratique O(n 2 ) , et complexité du temps cubique O(n 3 ) .

6. Complexité temporelle exponentielle : Big O(2n) Complexité

La complexité temporelle exponentielle signifie que le temps d'exécution d'un algorithme double à chaque ajout à l'ensemble de données d'entrée.

Par exemple, le problème de générer tous les sous-ensembles d'un ensemble est d'une complexité temporelle exponentielle :

Extrait de code 
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;  } }>

Complexité temporelle factorielle : complexité Big O(n !)

La complexité temporelle factorielle signifie que le temps d'exécution d'un algorithme augmente de manière factorielle avec la taille de l'entrée. Cela se voit souvent dans les algorithmes qui génèrent toutes les permutations d’un ensemble de données.

Voici un exemple d'algorithme de complexité temporelle factorielle, qui génère toutes les permutations d'un tableau :

Extrait de code 
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  }  } }>

Si nous traçons les exemples de notation Big O les plus courants, nous aurions un graphique comme celui-ci :

analyse asymptotique

Comment déterminer la notation Big O ?

Notation grand O est une notation mathématique utilisée pour décrire le comportement asymptotique d'une fonction à mesure que son entrée devient infiniment grande. Il fournit un moyen de caractériser l’efficacité des algorithmes et des structures de données.

Étapes pour déterminer la notation Big O :

1. Identifiez le terme dominant :

  • Examinez la fonction et identifiez le terme avec l’ordre de croissance le plus élevé à mesure que la taille de l’entrée augmente.
  • Ignorez les facteurs constants ou les termes d’ordre inférieur.

2. Déterminez l’ordre de croissance :

  • L'ordre de croissance du terme dominant détermine la notation Big O.

3. Écrivez la notation Big O :

  • La notation Big O s'écrit O(f(n)), où f(n) représente le terme dominant.
  • Par exemple, si le terme dominant est n^2, la notation Big O serait O(n^2).

4. Simplifiez la notation (facultatif) :

  • Dans certains cas, le Marque Big O n peut être simplifié en supprimant les facteurs constants ou en utilisant une notation plus concise.
  • Par exemple, O(2n) peut être simplifié en Sur).

Exemple:

conversion de chaîne en entier en Java

Fonction : f(n) = 3n3+ 2n2+5n+1

  1. Terme dominant : 3n3
  2. Ordre de croissance : cubique (n3)
  3. Notation grand O : O(n3)
  4. Notation simplifiée : O(n3)

Exemples mathématiques d'analyse d'exécution :

Le tableau ci-dessous illustre l'analyse d'exécution de différents ordres d'algorithmes à mesure que la taille d'entrée (n) augmente.

njournal(n)nn * journal(n)n ^ 22^nn!
dix1dixdix10010243628800
vingt2 996vingt59,940010485762.432902e+1818

Exemples algorithmiques d'analyse d'exécution :

Le tableau ci-dessous catégorise les algorithmes en fonction de leur complexité d'exécution et fournit des exemples pour chaque type.

TaperNotationExemples d'algorithmes
LogarithmiqueO (log n)Recherche binaire
LinéaireSur)Recherche linéaire
SuperlinéaireO (n journal n)Tri par tas, tri par fusion
PolynômeO(n^c)Multiplication matricielle de Strassen, tri à bulles, tri par sélection, tri par insertion, tri par seau
ExponentielO(c^n)La tour de Hanoi
FactorielleSur!)Expansion déterminante par les mineurs, algorithme de recherche par force brute pour le problème du voyageur de commerce

Classes d'algorithmes avec nombre d'opérations et temps d'exécution :

Vous trouverez ci-dessous les classes d'algorithmes et leurs temps d'exécution sur un ordinateur exécutant 1 million d'opérations par seconde (1 sec = 10 6 µsec = 10 3 msec) :

Cours de notation Big O

f(n)

Analyse Big O (nombre d'opérations) pour n = 10

Temps d'exécution (1 instruction/μsec)

constante

O(1)

1

1 μsec

logarithmique

O (connexion)

3.32

3 μsec

linéaire

Sur)

dix

10 μsec

O (nlogn)

O (nlogn)

33.2

33 μsec

quadratique

Sur2)

dix2

100 μsec

cubique

Sur3)

dix3

exemples de modèles

1 ms

exponentiel

O(2n)

1024

10 ms

factorielle

Sur!)

dix!

3,6288 secondes

Comparaison de la notation Big O, de la notation Big Ω (Omega) et de la notation Big θ (Theta) :

Vous trouverez ci-dessous un tableau comparant la notation Big O, la notation Ω (Omega) et la notation θ (Theta) :

NotationDéfinitionExplication
Grand O (O)f(n) ≤ C * g(n) pour tout n ≥ n0Décrit la limite supérieure du temps d’exécution de l’algorithme dans le pire cas .
Ω (Oméga)f(n) ≥ C * g(n) pour tout n ≥ n0Décrit la limite inférieure du temps d’exécution de l’algorithme dans le meilleur cas .
θ (Thêta)C1* g(n) ≤ f(n) ≤C2* g(n) pour n ≥ n0Décrit à la fois les limites supérieure et inférieure de l'algorithme. temps de fonctionnement .

Dans chaque notation :

  • f(n) représente la fonction analysée, généralement la complexité temporelle de l’algorithme.
  • g(n) représente une fonction spécifique qui délimite f(n) .
  • C, C1​, et C2 sont des constantes.
  • n 0 ​ est la taille minimale d'entrée au-delà de laquelle l'inégalité persiste.

Ces notations sont utilisées pour analyser les algorithmes en fonction de leur dans le pire des cas (Big O) , meilleur des cas (Ω) , et cas moyen (θ) scénarios.

Questions fréquemment posées sur la notation Big O :

Question 1. Qu'est-ce que la notation Big O ?

Répondre: La notation Big O est une notation mathématique utilisée pour décrire la limite supérieure de la complexité temporelle d'un algorithme en termes de croissance par rapport à la taille de l'entrée.

Question 2. Pourquoi la notation Big O est-elle importante ?

Répondre: Il nous aide à analyser et à comparer l'efficacité des algorithmes en nous concentrant sur le pire des cas et en comprenant comment leurs performances évoluent avec la taille des entrées.

Question 3. Comment la notation Big O est-elle calculée ?

Répondre: La notation Big O est déterminée en identifiant l'opération dominante dans un algorithme et en exprimant sa complexité temporelle en termes de n, où n représente la taille d'entrée.

Question 4. Que signifie O(1) dans la notation Big O ?

Répondre: O(1) signifie une complexité temporelle constante, indiquant que le temps d'exécution d'un algorithme ne change pas quelle que soit la taille de l'entrée.

Question 5. Quelle est la signification des différentes complexités Big O comme O(log n) ou O(n^2) ?

Répondre: Différentes complexités telles que O(log n) ou O(n^2) représentent la façon dont les performances d'un algorithme évoluent à mesure que la taille de l'entrée augmente, fournissant ainsi un aperçu de son efficacité et de son évolutivité.

Question 6. La notation Big O peut-elle également être appliquée à la complexité de l'espace ?

Répondre: Oui, Big O Notation peut également être utilisé pour analyser et décrire la complexité spatiale d’un algorithme, en indiquant la quantité de mémoire dont il a besoin par rapport à la taille d’entrée.

Article associé: