formations/algo/AlgoApprofondie/cours/complexite.txt

100 lines
3.4 KiB
Plaintext
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Notion de complexité d'un algorithme
====================================
Définition
-----------
Lanalyse de la complexité dun algorithme consiste à évaluer les ressources
consommées par lalgorithme lors de lexécution
deux critères dévaluation
- le coût en temps (nombre dopérations)
- le coût en espace, (quantité de mémoire)
principes de base
-----------------
Caractériser la quantité de ressources consommées en fonction de la
taille des données sur lesquelles lalgorithme est appliqué.
Evaluer le coût exact est difficile, on exprimera donc seulement un
ordre de grandeur
On peut approximer la complexité des algorithmes.
C'est utile pour pouvoir comparer des algorithmes.
complexité
estimer la complexité d'un algorithme, c'est estimer le nombre de calculs qu'il utilise.
Si f est la fonction caractérisant exactement le coût dun algorithme et n
la taille des données, on sintéresse à la façon dont augment f(n) lorsque n augmente
on va montrer que f(n) n'augmente pas plus vite quune autre fonction
g(n). Du point de vue mathématique, on dit que la fonction f est dominée
asymptotiquement par la fonction g ce qui se note f = O(g)
- Complexité temporelle : cest le nombre dop«erations effectuées par
une machine qui exécute lalgorithme.
- Complexité spatiale : cest le nombre de positions mémoire utilisées par
une machine qui exécute lalgorithme.
définition mathématique
-----------------------
- si f est la fonction caractérisant exactement le coût dun algorithme
- et n la taille des données
- on s'intéresse à la façon dont croît f(n) lorsque n croît
- on va montrer que f (n) ne croît pas plus vite quune autre fonction g(n)
Du point de vue mathématique, on dit que la fonction f est dominée
asymptotiquement par la fonction g ce qui se note f= O(g)
::
f = O(g) ssi il existe k, il existe n 0 , pour tout n, n > n 0 implique
f(n) inférieur ou egal k.g (n)
exemples
---------
- O(n) : progression linéaire
- O(n^2) : progression quadratique
- O(n^p) : progression polynomiale
- O(p^n ) : progression exponentielle
- O(log(n)): progression logarithmique
Problèmes NP-complets
----------------------
En théorie de la complexité, un problème NP-complet (c'est-à-dire un problème
complet pour la classe NP) est un problème de décision vérifiant les
propriétés suivantes :
- Il est possible de vérifier une solution efficacement (en temps
polynomial) ; la classe des problèmes vérifiant cette propriété est notée
NP ;
- Tous les problèmes de la classe NP se ramènent à celui-ci via une
réduction polynomiale ; cela signifie que le problème est au moins
aussi difficile que tous les autres problèmes de la classe NP.
- Un problème NP-difficile est un problème qui remplit la seconde
condition, et donc peut être dans une classe de problème plus large et
donc plus difficile que la classe NP.
Bien qu'on puisse vérifier rapidement toute solution proposée d'un
problème NP-complet, on ne sait pas en trouver efficacement. C'est le
cas, par exemple, du problème du voyageur de commerce ou de celui du
problème du sac à dos.
Tous les algorithmes connus pour résoudre des problèmes NP-complets
ont un temps d'exécution exponentiel en la taille des données d'entrée
dans le pire cas, et sont donc inexploitables en pratique même pour
des instances de taille modérée.