Notation Big O

11.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 l'algorithme se scale et comment sa performance change avec l'augmentation de la quantité 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 significatifs, permettant ainsi 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 d'un tableau par son 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 : parcours simple de tous les éléments d'un tableau.

O(log n) — Complexité logarithmique :

• Le temps d'exécution de l'algorithme croît logarithmiquement 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 force brute.

Note. Vous en apprendrez plus sur la recherche binaire, le tri à bulles et le "problème du sac à dos" dans les prochaines conférences.

11.2 Interprétation de la notation Big O

Comment interpréter et utiliser la notation Big O ?

Ignorer les constantes et les termes moins significatifs : Big O décrit l'ordre de croissance de la fonction, en ignorant les constantes et les termes moins significatifs. 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, afin d'évaluer sa complexité maximale.

Ignorer les constantes

Considérons des exemples d'ignorance des constantes et des termes moins significatifs :

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. Par conséquent, 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.

11.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é en temps O(n^2).
• L'algorithme B a une complexité en temps O(n log n).

Pour de petites valeurs de n, l'algorithme A peut fonctionner plus rapidement en raison de constantes plus petites, 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é en temps O(n).
• L'algorithme Y a une complexité en temps O(1).

L'algorithme Y sera toujours plus rapide, indépendamment de 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é en temps O(n^2) dans le pire des cas, lorsque le tableau est trié dans l'ordre inverse. Cela signifie que pour chaque élément dans le tableau, il faudra une comparaison et, éventuellement, un échange avec chaque autre élément.

Exemple 2 :

La recherche binaire a une complexité en temps O(log n) dans le pire des cas. Cela signifie que même dans le pire des 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 les données, l'un avec une complexité en temps O(n^2), et l'autre avec O(n log n), et que nous augmentons la taille des données de 1000 éléments à 10 000 éléments, la différence de performance sera significativement perceptible.

• L'algorithme avec O(n^2) exécutera environ 100 000 000 d'opérations pour 10 000 éléments.
• L'algorithme avec O(n log n) exécutera 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 manière exponentielle.

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

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

1

Опрос

Structures de données,  52 уровень,  4 лекция

недоступен

Structures de données

Structures de données

Открыть