Cours Algorithmique : Complexité des Algorithmes
- L'analyse par récurrence.
- Les Problèmes NP -complets.
Le plus souvent le temps de calcul est le plus important. Il faut considérer le temps et l’espace dans le pire des cas, c'est-à-dire définir un majorant de la complexité en temps et en espace. Pour cela, on effectue une analyse de l’algorithme (analyse souvent facile, souvent difficile et quelquefois impossible).
Le temps (ou espace) dépend des entrées. On n’a donc pas de majorant universel. Il faut considérer le temps comme fonction de la taille n des entrées, en nombres, bits, caractères et chercher à majorer cette fonction. On obtient une complexité souvent exprimée t(n)=O(f(n) c'est-à-dire il existe N et c tels que si n > =N, alors t(n) < =cf(n).
Ici, nous considérons l'analyse du temps d'un algorithme donné. La complexité d'un problème peut être définie (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 ...
On utilise ce type d’analyse dans le cas des boucles où le nombre d'itérations n'est pas évident. On peut notamment citer les exemples suivants :
Prenons par exemple le problème 3SAT : expression booléenne qui est la conjonction de clauses de la forme (u ou v ou w) où u v et w sont des variables ou négations de variables. L’algorithme brut consiste à considérer les 2n affectations possibles des n variables. Dans le cas ou n=3, la manière la plus efficace consiste à diviser l’algorithme en trois sous problèmes :
La taille des sous-problèmes est donc respectivement n-1, n-2, n-3. Le majorant est alors donné par t(n)=t(n-1+t(n-2)+t(n-3) c'est-à-dire 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).
Mais ce n’est pas optimal.
-------------------------------------------------------------------------------------------------------
Précédent : Les Fonctions sur les nombres
Suivant : Étude Fonctionnement d'un Programme
- Les Problèmes NP -complets.
1 Complexité des algorithmes
1.1 Complexité des algorithmes : temps et espace
Le plus souvent le temps de calcul est le plus important. Il faut considérer le temps et l’espace dans le pire des cas, c'est-à-dire définir un majorant de la complexité en temps et en espace. Pour cela, on effectue une analyse de l’algorithme (analyse souvent facile, souvent difficile et quelquefois impossible).
1.2 Comme fonction de la taille des entrées notation O( )
Le temps (ou espace) dépend des entrées. On n’a donc pas de majorant universel. Il faut considérer le temps comme fonction de la taille n des entrées, en nombres, bits, caractères et chercher à majorer cette fonction. On obtient une complexité souvent exprimée t(n)=O(f(n) c'est-à-dire il existe N et c tels que si n > =N, alors t(n) < =cf(n).
On dit aussi omicron, omega, OMEGA, THETA.
1.3 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éfinie (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 ...
1.4 Analyses
1.4.1 Analyses simples du texte du programme
- Une boucle 1 à n prend le temps O(n)
- Deux boucles imbriquées 1 à n prennent temps O(n2), et ensuite de suite.
- Une recherche dichotomique sur n possibilités prend le temps O(logn)
- Algorithme d’Euclide pour pgcd(m,n) (supposons m > =n); m remplacé en 2 itérations par m mod n prend dans le pire des cas [(m-1)/2 ] c'est-à-dire O(logn). Mais est-ce vraiment possible ?
1.4.2 Analyses plus complexes du comportement du programme
On utilise ce type d’analyse dans le cas des boucles où le nombre d'itérations n'est pas évident. On peut notamment citer les exemples suivants :
- chercher quelque chose: s'il y a une borne évidente sur le nombre de cas à considérer, ça donne un majorant mais peut-être très grossier
- processus itératif qui converge, peut-être, très lentement
- boucles très simples mais où le calcul du nombre d'itérations semble très difficile
Par exemple l’algorithme suivant :
Tant que (n>1)
si (n~pair) alors n:=n/2;
sinon n:=3n+1
fin si
fin tant que
si (n~pair) alors n:=n/2;
sinon n:=3n+1
fin si
fin tant que
Personne ne peut garantir que ce programme s’arrête pour tout n positif!
1.4.3 Analyses par récurrence
Prenons par exemple le problème 3SAT : expression booléenne qui est la conjonction de clauses de la forme (u ou v ou w) où u v et w sont des variables ou négations de variables. L’algorithme brut consiste à considérer les 2n affectations possibles des n variables. Dans le cas ou n=3, la manière la plus efficace consiste à diviser l’algorithme en trois sous problèmes :
- u vrai,
- u faux mais v vrai,
- u et v faux mais w vrai
La taille des sous-problèmes est donc respectivement n-1, n-2, n-3. Le majorant est alors donné par t(n)=t(n-1+t(n-2)+t(n-3) c'est-à-dire 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).
Mais ce n’est pas optimal.
1.4.4 Les problèmes NP-complets
- Le meilleur algorithme connu est THETA(2n) (SAT)
- Rarement n! (isomorphisme de (sous-)graphes)
- Ou an avec a < 2
- Ou 2racine(n)
1.4.5 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 du nombre d’appel
- 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 programme, cela donne un majorant déterministe amorti
- par exemple, une fonction de mise à jour d'une structure de données
-------------------------------------------------------------------------------------------------------
Précédent : Les Fonctions sur les nombres
Suivant : Étude Fonctionnement d'un Programme
Article plus récent Article plus ancien
