Complexité d'un algorithme.

Introduction.

Définition

Un algorithme est une succession de taches permettant de résoudre un problème.

Si en théorie avoir un algorithme pour résoudre un problème permet de le résoudre, en pratique c'est plus compliqué car intervient la contrainte du temps : chaque tache demande du temps pour être exécutée et au final le temps d’exécution peut être considérable.

Si vous avez besoin de temps réel (arrêt automatique d'une voiture), vous ne pouvez avoir un algorithme qui prend une seconde à s’exécuter. Des systèmes de cryptographie peuvent être cassé en décomposant un nombre en produit de facteurs, on s'est le faire mais pour des grands nombres cela demande des siècles. A l'usage les algorithmes de cryptage offrent une bonne sécurité.

Étudier le nombre d'opérations nécessaire à la résolution d'un problème revient à étudier sa complexité.

Remarque

On étudiera ici le nombre d'opérations que demande un algorithme mais il existe d'autres contraintes issues d'un ordinateur réel, on peut alors étudier son besoin en mémoire, sa précision (les flottants ne représente qu'imparfaitement les réels)...

Remarque

Un algorithme peut selon les données être plus ou moins efficace, l'étude de la complexité peut se faire sur le pire des cas, sur les cas moyens,...

Exemple

Le T.P. sur la méthode de Horner montre complexité en nombres d'opération de la méthode de la naïve du calcul de l'image par un polynôme de degré n est $\frac{n(n+1)}{2} + n$ celui de la méthode de Horner est 2n.

Ordre de grandeur.

Les comparaisons asymptotiques de fonctions est du niveau BAC+2, on ne rentrera pas dans les détails.

Soit deux fonctions f et g définient sur $\mathbf{R}$ sont de même ordre si il existe deux constantes k₁ et k₂ tel que pour tout n :

$$ k_1 g(x) \le f(x) \le k_2 g(x) $$

dés que x est suffisamment grand.

La notation utilisée est $f = \Theta(g)$. On trouve aussi la notation $f = O(g)$ qui a plus le sens f est dominé asymptotiquement par g.

Exemple

$ x^3 + 2x^2 + 3x +1$ est du même ordre que $x^3$ quand x est grand $2x^2+3x+1$ est négligeable devant $x^3$. en informatique on peut dire que si un programme met une journée à s’exécuter alors une ou deux minutes de plus n'est pas grave.
$2x^3$ est du même ordre que $x^3$, le coefficient multiplicatif n'a pas d'importance, en terme d'informatique deux algos diffère d'un coefficient multiplicateur il suffit de changer de machine ou de langage.

Pour trouver l'ordre de grandeur, il faut trouver dans l'expression le terme qui domine. Pour un polynôme c'est le terme de plus haut degré.

Q.C.M.

Les fonctions qui ont même ordre de grandeur asymtotique que 3n² + 3n + 1 sont :

n²
3n+1
3n²
4n²+4

Q.C.M.

L'ordre de grandeur asymptotique de (x-2)(x-3)(x-2) est un :

$\Theta(1)$
$\Theta(x)$
$\Theta(x^2)$
$\Theta(x^3)$

Q.C.M.

La complexité de la méthode de Horner est :

$\Theta(1)$
$\Theta(x)$
$\Theta(x^2)$
$\Theta(x^3)$

Q.C.M.

La complexité de la méthode naïve du calcul d'un polynôme est :

$\Theta(1)$
$\Theta(x)$
$\Theta(x^2)$
$\Theta(x^3)$

Echelle de complexité

Pour tester les fonction on pourra utiliser le wrapper suivant :

$\Theta(1)$

Un algorithme est en $\Theta(1)$ quand il ne dépend pas de la taille de la donnée et que son cout est donc constant

Exemple

Accéder à un élèment d'un tableau ou d'un dictionnaire est en $\Theta(1)$ par exemple.

L'algorithme suivant permet de calculer la somme des n premiers entiers 1 + 2 + ... + n.

Remarque

Dans un ordinateur la taille des entiers est généralement de 32 bits et les circuits sont fait pour des opérations sur des entiers de cette taille, si l'entier dépasse 32 bits les opérations sont plus lentes.

Remarque

A retenir : si le nombre d'instructions du programme ne dépend pas de n alors le programme est en $\Theta(1)$. Si il n'y a pas de boucles dépendant de la taille de la donnée alors le programme est en $\Theta(1)$. (Attention si vous avez
for i in range(3):
alors la boucle ne dépend pas de la taille de la donnée.)

$\Theta(ln(n))$

La fonction logarithme est une fonction très importante, c'est l'inverse de la fonction exponentielle et elle est au programme de terminale. En physique vous la rencontrez au moment de parler du PH.

Si un algorithme est en ln(n) alors son coup croit très doucement en fonction des données, doubler la taille des données ne provoque qu'un nombre fixe d'opération en plus.

Attachée à la fonction ln il existe des fonction logarithmes qui sont liées, log_n et qui diffère d'un coefficient multiplicateur.

Pour en donner une version entière log₂(n) est le nombre k le plus grand tel que 2^k ≤ n. Par exemple log₂(7) = 2 car 2

Exemple

La recherche dichotomique est l'exemple type d'un algorithme en $\Theta(ln(n))$. Voici un exemple pour la recherche du plus grand plus petit.

Remarque

A retenir : si le nombre d'instructions augmente de 1 si on double la taille des données alors le programme est en $\Theta(ln(n))$.

$\Theta(n)$

Un algorithme est en $\Theta(n)$ s'il est proportionnel à la taille des données, des données deux fois plus grande provoque un doublement du temps d’exécution.

Exemple

Grossièrement un algorithme est en $\Theta(n)$ si il y a une boucle de la taille de la donnée.

La recherche d'une donnée dans une liste non ordonnée.

Le calcul de l'image d'un nombre par une fonction polynôme avec la méthode de Horner.
Le calcul de la somme des n premiers entiers par une boucle. (Si on considère la valeur de n et pas sa place en mémoire).

Remarque

A retenir : si le nombre d'instructions double si on double la taille des données alors le programme est en $\Theta(n))$. On reconnait se type d'algorithme s'il y a une boucle qui dépend de la taille de la donnée.

$\Theta(nln(n))$

Si un algorithme est en $\Theta(nln(n))$ alors il est presque linéaire.

Exemple

Les meilleurs algorithmes de tri par comparaison ont cette complexité (c'est la limite théorique, on ne peut pas faire mieux par comparaison).

Lien

$\Theta(n²)$

Si un algorithme est en $\Theta(n²)$ alors doubler la taille quadruple le temps d’exécution.

Exemple

Si un algorithme a une boucle de taille n dans une autre de taille n alors il est un $\Theta(n²)$.

Généralement travailler dans une matrice (une image par exemple) donne des algorithme en $\Theta(n²)$. C’était le cas de la transformation en noir et blanc ou du contour d'une image.

Si on libère la dimension de la taille de la grille du puissance 4 alors chercher une victoire (avec la méthode proposée dans mon T.D.) est en $\Theta(n²)$.
Les algorithmes de tri au programme cette année sont en n².

Remarque

A retenir : si le nombre d'instructions quadruple si on double la taille des données alors le programme est en $\Theta(n²))$.On reconnait ce genre d'algorithme si il y a deux boucles imbriquées qui dépendent de la taille des données.

$\Theta(n^3$)

En pratique les algorithmes en $\Theta(n^3$) commencent à être long. Doubler la donnée multiplie par 8 le temps d’exécution.

Exemple

La multiplication matricielle (très courante après le bac) est de façon basique en $\Theta(n^3)$.

Détermination du volume par un rapport des points.

Remarque

A retenir : si le nombre d'instructions quadruple si on double la taille des données alors le programme est en $\Theta(n²))$.On reconnait ce genre d'algorithme si il y a trois boucles imbriquées qui dépendent de la taille des données.

Complexité exponentielle.

Quand des algorithmes sont exponentielles $\Theta(2^n)$ ils sont rapidement peu utilisables. On passe alors à d'autres algorithmes qui a défaut de donner des résultats exacts donnent des très bons résultats à des coûts moindres.

Exemple

Trouver tous les sous ensemble d'un ensemble est un problème exponentielle.

Le problème du sac à dos (que nous verrons plus tard) ou le voyageur de commerce (avec un algorithme avancé) sont des algorithmes exponentielles.

Remarque

A retenir : si le nombre d'instructions est élevé au carré (ou au cube...) si on double la taille des données alors le programme est en $\exp(n)$.

Complexité factorielle.

Encore pire que les problèmes exponentielles.

Exemple

Effectuer toutes les permutations possibles d'un ensemble :

Le voyageur de commerce version naïve qui consiste à essayer toutes les possibilités se trouve alors dans la complexité factorielle et est totalement inutilisable en pratique si le nombre de villes est un peu grand.

Comparatif du temps d'execution.

Donner le nombre limite d'opérations : .

Alors le nombre donné à l'algorithme doit être au plus de :

$\Theta(1)$ : potentiellement infini.

$\Theta(ln(n))$ :

$\Theta(n)$ :

$\Theta(nln(n))$ :

$\Theta(n^2)$ :

$\Theta(n^3)$ :

$\Theta(2^n)$ :

$\Theta(n!)$ :

Donner la taille de la donnée : .

Alors, sur une machine qui fait 1000 000 000 opérations par seconde (1Ghz), le temps de calcul est au moins :

$\Theta(1)$ : 1 nano seconde =$10^{-9}$.

$\Theta(ln(n))$ :

$\Theta(n)$ :

$\Theta(nln(n))$ :

$\Theta(n^2)$ :

$\Theta(n^3)$ :

$\Theta(2^n)$ :

$\Theta(n!)$ :