Complexité et analyse des algorithmes
L'analyse des algorithmes quantifie la manière dont le temps d'exécution et la mémoire d'un algorithme augmentent avec la taille de l'entrée, fournissant le vocabulaire et les outils asymptotiques utilisés pour comparer les algorithmes et identifier les problèmes intrinsèquement difficiles.
Definition
L'analyse des algorithmes est l'étude des ressources computationnelles — principalement le temps et l'espace — qu'un algorithme consomme en fonction de la taille de son entrée, ainsi que des techniques utilisées pour dériver, exprimer et comparer ces bornes de ressources.
Scope
Ce domaine couvre la mesure et la comparaison de l'utilisation des ressources algorithmiques : la notation asymptotique (grand O, grand Oméga, grand Thêta), la résolution des récurrences issues des algorithmes récursifs, l'analyse amortie des séquences d'opérations, et les bases des classes de complexité computationnelle et de la NP-complétude telles qu'elles s'appliquent à la conception d'algorithmes. Il aborde les coûts dans le pire des cas, en moyenne et amortis, ainsi que la distinction entre problèmes traitables et intraitables. La théorie plus large de la calculabilité (calculabilité, classes de complexité formelles) appartient à un sous-domaine distinct ; ici, l'accent est mis sur l'analyse d'algorithmes concrets.
Sub-topics
Core questions
- Comment l'utilisation des ressources d'un algorithme est-elle exprimée indépendamment des détails de la machine et de l'implémentation ?
- Que nous apprennent respectivement les analyses dans le pire des cas, en moyenne et amorties ?
- Comment les récurrences produites par les algorithmes récursifs sont-elles résolues pour obtenir des bornes asymptotiques ?
- Comment pouvons-nous établir des bornes inférieures montrant qu'aucun algorithme ne peut faire mieux ?
- Que signifie pour un problème d'être NP-complet, et pourquoi est-ce important pour la conception ?
Key concepts
- grand O, grand Oméga, grand Thêta
- analyse dans le pire des cas et en moyenne
- relations de récurrence
- théorème maître
- analyse amortie
- bornes inférieures
- temps polynomial
- NP-complétude
Key theories
- Notation asymptotique
- Grand O, grand Oméga et grand Thêta décrivent le taux de croissance de l'utilisation des ressources à mesure que la taille de l'entrée augmente, en faisant abstraction des constantes et des termes d'ordre inférieur pour permettre une comparaison des algorithmes indépendante de la machine.
- Traitabilité et NP-complétude
- Les problèmes résolubles en temps polynomial sont considérés comme traitables ; les problèmes NP-complets sont ceux auxquels tous les problèmes de NP se réduisent, et trouver un algorithme polynomial pour l'un d'entre eux résoudrait tous les autres, une question (P versus NP) qui reste ouverte.
Clinical relevance
L'analyse des algorithmes guide chaque décision d'ingénierie concernant le choix de l'algorithme ou de la structure de données à utiliser, en prédisant comment les systèmes évoluent à mesure que les données augmentent. Reconnaître qu'un problème est NP-difficile indique aux praticiens de rechercher des méthodes d'approximation, heuristiques ou de cas particuliers plutôt qu'un algorithme polynomial exact, ce qui façonne le travail dans les domaines de l'optimisation, de la planification et du calcul à grande échelle.
History
La notation asymptotique a été importée en informatique depuis la théorie analytique des nombres et popularisée par Donald Knuth dans les années 1960 et 1970. La théorie de la NP-complétude a été fondée par Stephen Cook (1971) et étendue par Richard Karp (1972), remodelant la conception des algorithmes autour de la frontière entre les problèmes traitables et intraitables.
Debates
- P versus NP
- Savoir si tout problème dont les solutions peuvent être vérifiées rapidement peut également être résolu rapidement (P = NP) est la question ouverte centrale de l'informatique théorique ; il est largement conjecturé que P n'est pas égal à NP, mais aucune preuve n'existe.
Key figures
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
Related topics
Seminal works
- cormen2009
- knuth1976bigo
- kleinberg2006
Frequently asked questions
- Quelle est la différence entre l'analyse dans le pire des cas et l'analyse en moyenne ?
- L'analyse dans le pire des cas borne l'utilisation des ressources sur l'entrée la plus défavorable de chaque taille, offrant une garantie. L'analyse en moyenne estime l'utilisation attendue des ressources sur une distribution d'entrées, ce qui peut être plus représentatif des performances typiques mais dépend des hypothèses concernant la distribution des entrées.
- Si un problème est NP-complet, est-il désespéré de le résoudre ?
- Non. La NP-complétude signifie qu'aucun algorithme efficace n'est connu pour le pire des cas, mais les instances peuvent souvent être résolues avec des algorithmes d'approximation, des heuristiques, des algorithmes exponentiels suffisamment rapides en pratique, ou en exploitant une structure spéciale. Cela signale un changement de stratégie, pas une impossibilité.