Complexité des algorithmes
temps et espace

Comme fonction de la taille des entrées
notation O( ) etc.

Complexité d'un algorithme, pas d'un problème

Analyses simples du texte du programme

Analyses plus complexes du comportement du programme

Des boucles où le nombre d'itérations n'est pas évident

Analyses par récurrence

Solution de (quelques) récurrences
le théorème maître

Quand la récurrence a une forme régulière et simple
T(n) = a T(n/b) +f(n)
       = a2 T(n/b2) + af(n/b) +f(n)
       = alogb(n)T(1) + ... + ...
       = nlogb(a)T(1) + ... + ...
le plus souvent on a un des 3 cas suivants

``suffisamment'' défini exactement dans le livre
existence de cas qui ne sont pas couverts par ces 3 règles

Les problèmes NP-complets

Il existe pas mal de problèmes intéressants (une définition exacte suivra mais par exemple le problème 3SAT déjà énoncé) pour lesquels on ne sait pas s'il existe un algorithme efficace (polynomial) ou non. Mais, s'il existe un algorithme efficace pour l'un de ces problèmes, il en existe un aussi pour tous les autres!

Analyse pire cas, en moyenne, ou amortie




File translated from TEX by TTH, version 3.05.
On 21 Nov 2006, 17:36.