Complexité des algorithmes
temps et espace
- Le plus souvent le temps de calcul est le plus important
- Dans le pire des cas; donc chercher un majorant
- Analyse souvent facile, souvent difficile
- Quelquefois impossible
Comme fonction de la taille
des entrées
notation O( ) etc.
- Le temps (ou espace) dépend des entrées; pas de majorant
universel
- considérer le temps comme fonction de la taille n des entrées,
en nombres, bits, caractères; chercher à majorer cette fonction
- souvent exprimé t(n)=O(f(n) c'est-à-dire il existe N
et c tels que si n > =N, alors t(n) < =cf(n)
- aussi o, w, W, Q
Complexité d'un
algorithme, pas d'un problème
- Ici, nous considérons l'analyse du temps d'un algorithme donné
- La complexité d'un problème peut être défini
(approximativement) comme la complexité du meilleur algorithme possible
qui le résout
- l'analyse d'un algorithme fournit un majorant de la complexité
du problème
- Trouver un minorant est, le plus souvent, beaucoup plus difficile
...
Analyses simples du texte
du programme
- Une boucle 1 à n prend temps O(n)
- Deux boucles imbriquées 1 à n prennent temps O(n2),
etc.
- Recherche dichotomique sur n possibilités, temps O(logn)
- Algorithme de Euclid pour pgcd(m,n) (supposons m > =n); dans le
pire des cas m remplacé par ë (m-1)/2 û;
donc O(logn); est-ce vraiment possible ?
Analyses plus complexes
du comportement du programme
- Des boucles où le nombre d'itérations n'est pas évident
- chercher quelquechose où il n'y a pas de borne évidente
sur le nombre de cas à considérer
- processus itératif qui converge, peut-être, très
lentement
- f(n)=0 (n=1), f(n/2) (n pair),
f(3n+1) (sinon)!
Analyses par récurrence
- Exemple le problème 3SAT:
expression booléenne qui est la conjonction de clauses de la
forme (u ou v ou w) où u etc. sont de variables
ou négations de variables
- algorithme brut: considérer les 2n affectations
possibles des n variables
- meilleur: trois sous-problèmes : u vrai, u faux mais v vrai,
u et v faux mais w vrai
- taille des sous-problèmes n-1, n-2, n-3
- majorant donné par t(n)=t(n-1+t(n-2)+t(n-3)
- t(n)=O(an) où a est la (plus grande des) racine(s) de xn=xn-1+xn-2+xn-3, ou 1=x-1+x-2+x-3
( < 2)
- (pas optimal)
Les problèmes NP-complets
- Souvent le meilleur algorithme connu est Q(2n)
(SAT)
- Rarement n! (isomorphisme de (sous-)graphes)
- Ou an avec a ¹ 2
- Ou 2Ön
Analyse pire cas, en moyenne,
ou amortie
- Pour un algorithme seul, l'analyse dans le pire des cas est (probablement)
la plus importante
- pour une fonction qui va être appelée plusieurs fois
par un algorithme plus grand, c'est peut-être la moyenne
- Mais ceci ne peut donner qu'un majorant probabiliste pour l'algorithme
- Si on peut démontrer que le pire comportement de la fonction
ne se produit que rarement dans le fonctionnement du program, cela donne
un majorant déterministe amorti
- par exemple, une fonction de mise à jour d'une structure de
données
File translated from TEX by
TTH,
version 3.05.
On 15 Mar 2004, 12:00.