formations/algo/AlgoApprofondie/cours/complexite.txt

Notion de complexité d'un algorithme
====================================

Définition
-----------

L’analyse de la complexité d’un algorithme consiste à évaluer les ressources
consommées par l’algorithme lors de l’exécution

deux critères d’évaluation

- le coût en temps (nombre d’opé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 l’algorithme 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 d’un algorithme et n
la taille des données, on s’intéresse à la façon dont augment f(n) lorsque n augmente
on va montrer que f(n) n'augmente pas plus vite qu’une 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 : c’est le nombre d’op«erations effectuées par
  une machine qui exécute l’algorithme.

- Complexité spatiale : c’est le nombre de positions mémoire utilisées par
  une machine qui exécute l’algorithme.

définition mathématique
-----------------------


- si f est la fonction caractérisant exactement le coût d’un 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 qu’une 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.