Analyse asymptotique

L'analyse asymptotique décrit comment le temps d'exécution ou la mémoire d'un algorithme augmente à mesure que la taille de l'entrée devient grande, en utilisant des notations telles que grand O, grand Oméga et grand Thêta pour capturer le taux de croissance tout en ignorant les constantes et les termes d'ordre inférieur.

Definition

L'analyse asymptotique est la caractérisation du taux de croissance d'une fonction lorsque son argument tend vers l'infini ; dans l'analyse d'algorithmes, elle exprime comment l'utilisation du temps ou de l'espace s'adapte à la taille de l'entrée, en utilisant une notation d'ordre qui supprime les facteurs constants et les termes d'ordre inférieur.

Scope

Ce sujet couvre les notations asymptotiques utilisées pour caractériser l'utilisation des ressources — grand O (borne supérieure), grand Oméga (borne inférieure), grand Thêta (borne serrée), ainsi que les notations strictes petit o et petit oméga — ainsi que les classes de croissance standard (constante, logarithmique, linéaire, linéarithmique, polynomiale, exponentielle) et les règles de manipulation de ces bornes. Il explique pourquoi les facteurs constants et les termes d'ordre inférieur sont abstraits et comment les comparaisons asymptotiques prédisent le comportement de mise à l'échelle. Il exclut les mécanismes de résolution de récurrences utilisés pour obtenir ces bornes, qui sont traités séparément.

Core questions

• Que signifient respectivement grand O, grand Oméga et grand Thêta concernant la croissance d'une fonction ?
• Pourquoi les facteurs constants et les termes d'ordre inférieur sont-ils ignorés dans la comparaison asymptotique ?
• Comment les classes de croissance courantes sont-elles ordonnées de la croissance la plus lente à la plus rapide ?
• Comment les bornes asymptotiques prédisent-elles la mise à l'échelle d'un algorithme pour de grandes entrées ?
• Quand des algorithmes asymptotiquement plus lents peuvent-ils néanmoins être préférables en pratique ?

Key concepts

• notation grand O
• notation grand Oméga
• notation grand Thêta
• petit o et petit oméga
• classes de croissance
• facteurs constants
• termes d'ordre inférieur
• évolutivité

Key theories

Notation d'ordre

Grand O borne une fonction supérieurement à un facteur constant près, grand Oméga la borne inférieurement, et grand Thêta la borne des deux côtés ; ces définitions, standardisées pour l'informatique par Knuth, fournissent un langage précis pour les taux de croissance.

Dominance des taux de croissance

À mesure que la taille de l'entrée augmente, les termes d'ordre supérieur dominent, de sorte que la classe asymptotique d'un algorithme (par exemple, linéarithmique versus quadratique) détermine finalement son évolutivité, indépendamment des facteurs constants.

Clinical relevance

La notation asymptotique est la lingua franca pour discuter de l'efficacité des algorithmes : elle permet aux ingénieurs de comparer des algorithmes candidats, de prédire si un système s'adaptera à des charges de travail plus importantes, et de communiquer des garanties de performance dans la documentation, les entretiens, et l'analyse des bibliothèques et des standards.

History

Les notations grand O et les notations associées sont apparues au XIXe siècle dans la théorie analytique des nombres avec Bachmann et Landau (d'où la 'notation de Landau'). Donald Knuth les a adaptées et standardisées pour l'analyse des algorithmes dans les années 1960 et 1970, y compris une note de 1976 clarifiant l'utilisation de grand Oméga et grand Thêta en informatique.

Key figures

• Donald Knuth
• Paul Bachmann
• Edmund Landau

Seminal works

• knuth1976bigo
• cormen2009

Frequently asked questions

Un grand O plus petit signifie-t-il toujours un algorithme plus rapide ?

Pas nécessairement pour une taille d'entrée donnée. Grand O décrit la croissance lorsque la taille de l'entrée tend vers l'infini et masque les facteurs constants, de sorte qu'un algorithme avec une classe asymptotique moins bonne peut être plus rapide sur de petites entrées. C'est le meilleur guide pour les grandes entrées et l'évolutivité.

Quelle est la différence entre grand O et grand Thêta ?

Grand O ne donne qu'une borne supérieure de croissance, indiquant que l'algorithme n'est pas pire qu'un certain taux. Grand Thêta donne une borne serrée, affirmant que la croissance correspond à ce taux à la fois supérieurement et inférieurement. Dire qu'un algorithme est Thêta(n log n) est une affirmation plus forte et plus précise que O(n log n).