Notation Big O : concepts de base

2.1 Définition de la notation Big O.

La notation Big O est une notation mathématique utilisée pour décrire la limite supérieure du temps d'exécution ou de la consommation de ressources d'un algorithme en fonction de la taille des données d'entrée. Elle aide à déterminer comment bien l'algorithme passe à l'échelle et comment ses performances changent avec l'augmentation du volume de données.

La notation Big O se concentre sur les aspects les plus significatifs de l'algorithme, en ignorant les constantes et les termes moins importants, ce qui permet de se concentrer sur le comportement à long terme de l'algorithme.

Notations principales :

O(1) — Complexité constante :

• Le temps d'exécution de l'algorithme ne dépend pas de la taille des données d'entrée.
• Exemple : accès à un élément de tableau par index.

O(n) — Complexité linéaire :

• Le temps d'exécution de l'algorithme dépend linéairement de la taille des données d'entrée.
• Exemple : simple parcours de tous les éléments d'un tableau.

O(log n) — Complexité logarithmique :

• Le temps d'exécution de l'algorithme augmente de façon logarithmique avec l'augmentation de la taille des données d'entrée.
• Exemple : recherche binaire dans un tableau trié.

O(n^2) — Complexité quadratique :

• Le temps d'exécution de l'algorithme dépend quadratiquement de la taille des données d'entrée.
• Exemple : tri à bulles, tri par insertion.

O(2^n) — Complexité exponentielle :

• Le temps d'exécution de l'algorithme dépend exponentiellement de la taille des données d'entrée.
• Exemple : résolution du problème du sac à dos par une recherche exhaustive.

2.2 Interprétation de la notation Big O.

Comment interpréter et utiliser la notation Big O ?

Ignorer les constantes et les termes moins importants :

Big O décrit l'ordre de croissance d'une fonction, en ignorant les constantes et les termes moins importants. Par exemple, O(2n) et O(3n) sont interprétés comme O(n).

Comparer les algorithmes :

Big O permet de comparer les algorithmes selon leur efficacité asymptotique. Par exemple, un algorithme avec O(n log n) est plus efficace qu'un algorithme avec O(n^2) pour de très grandes quantités de données.

Analyse du pire cas :

Big O est généralement utilisé pour analyser le pire cas du temps d'exécution d'un algorithme, ce qui permet d'évaluer sa complexité maximale.

Ignorer les constantes.

Ignorer les constantes et les termes moins importants

Exemple 1:

Considérons deux fonctions :

• f(n) = 3n + 2
• g(n) = 5n + 1

Les deux fonctions ont une complexité linéaire car le terme dominant dans chaque fonction est n. Donc, les deux fonctions sont interprétées comme O(n), malgré les différences dans les coefficients et les termes supplémentaires.

Exemple 2 :

Considérons deux fonctions :

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Les deux fonctions ont une complexité quadratique car le terme dominant est n^2. Les deux expressions sont interprétées comme O(n^2), malgré les différences dans les autres termes et coefficients.

2.3. Comparaison des algorithmes

1. Comparaison des algorithmes sur de très grandes quantités de données

Exemple 1 :

• L'algorithme A a une complexité temporelle de O(n^2).
• L'algorithme B a une complexité temporelle de O(n log n).

Pour de petites valeurs de n, l'algorithme A peut être plus rapide en raison de constantes plus faibles, mais pour de grandes valeurs de n, l'algorithme B sera nettement plus rapide, car sa croissance est logarithmique et non quadratique.

Exemple 2 :

• L'algorithme X a une complexité temporelle de O(n).
• L'algorithme Y a une complexité temporelle de O(1).

L'algorithme Y sera toujours plus rapide, peu importe la taille de n, car O(1) signifie que le temps d'exécution de l'algorithme ne dépend pas de la taille des données d'entrée.

2. Analyse du pire cas

Exemple 1 :

L'algorithme de tri à bulles a une complexité temporelle de O(n^2) dans le pire cas, lorsque le tableau est trié dans l'ordre inverse. Cela signifie que pour chaque élément du tableau, il faudra une comparaison et, éventuellement, un échange avec chaque autre élément.

Exemple 2 :

La recherche binaire a une complexité temporelle de O(log n) dans le pire cas. Cela signifie que même dans le pire cas, le nombre d'étapes nécessaires pour trouver un élément dépendra logarithmiquement de la taille du tableau, ce qui est très efficace.

3. Impact sur la performance et la scalabilité

Exemple 1 :

Si nous avons deux algorithmes pour traiter des données, l'un avec une complexité temporelle de O(n^2), et l'autre avec O(n log n), et nous augmentons la taille des données de 1000 éléments à 10,000 éléments, la différence de performance sera significativement notable.

• L'algorithme en O(n^2) effectuera environ 100,000,000 d'opérations pour 10,000 éléments.
• L'algorithme en O(n log n) effectuera environ 40,000 opérations pour 10,000 éléments.

Exemple 2 :

Considérons un algorithme qui fonctionne en O(2^n). Si nous augmentons la taille des données d'entrée de 10 à 20 éléments, le nombre d'opérations augmente de façon exponentielle.

• Pour n = 10 : 2^10 = 1024 opérations.
• Pour n = 20 : 2^20 = 1,048,576 opérations.

Cela montre à quel point la complexité exponentielle devient impraticable pour de grandes valeurs de n.