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

Analyse pire cas, en moyenne, ou amortie




File translated from TEX by TTH, version 3.05.
On 8 Dec 2005, 12:32.

symboles bricolés pour netscape par sed