Complexité

Temps et espace d’exécution

Le temps d’exécution et la place mémoire requise caractérisent la complexité d’un programme. Sous UNIX, on mesure le temps d’exécution d’un programme au moyen de la commande time.

:; time wc session/log 
31 136 1044 session.log

real    0m0.08s
user    0m0.01s
sys     0m0.02s

Il tombe sous le sens qu’un programme mettra d’autant plus de temps à s’achever qu’il aura de données à traiter. Pour un même résultat, deux algorithmes équivalents ne verront sans doute pas leur temps d’exécution croître dans les mêmes proportions en fonction desdonnées à traiter. Exemple : Calculs du plus grand diviseur de $n$ . Première méthode :

i = n - 1 ;

while (0 != (n % i))
    /* pgd ≤ i const. de boucle */
    i = i - 1 ;
pgd = i ;

Deuxième méthode :

i = 2 ;
while (i <  et 0 != (n % i))     /* pgd > i const. de boucle */
    i = i + 1 ;

/* pgd = SI ( modulo ) ALORS  SINON 1 */
pgd = (0 == (n % i)) ? n/i : 1 ;

Complexité en tempsLa complexité d’un algorithme se mesure essentiellement en calculant le nombre d’opérations élémentaires pour traiter une donnée de taille. Les opérations élémentaires considérées sont
- le nombre de comparaisons (algorithmes de recherches)
- le nombre d’affectations (algorithmes de tris)
- Le nombre d’opérations ( $+, *$ ) réalisées par l’algorithme (calculs sur les matrices ou les polynômes).
Le coût d’un algorithme pour une donnée est le nombre d’opérations élémentaires nécessaires au traitement de la donnée et est noté
Complexité dans le pire des cas, exemple : recherche d’un nombre dans un tableau, alors qu’il n’y est pas :
$\mbox{Max}_{(n)} = \mbox{max}\{O(d_{1}), d_{i}\in D_{i} \}$
Complexité dans le meilleur des cas, ex : rechercher d’un nombre dans un tableau, alors qu’il est en première position :
$\mbox{Min}_{(n)} = \mbox{min}\{O(d_{1}), d_{i}\in D_{i}\}$
Complexité en moyenne

$\text{Moy}(n) = \sum_{d \subset D_{n}} p(d) O(d)$

où $(p(d)$ est la probabilité d’avoir en entrée la donnée $d$ parmi toutes les données de taille $n$ . Si toutes les données sont équiprobables, alors on a,

$\text{Moy} = \frac{1}{|D_{i}|}\sum_{d\in D_{n}}O(d)$

Espace mémoire

Il est quelquefois nécessaire d’étudier la complexité en mémoire lorsque l’algorithme requiert de la mémoire supplémentaire (tableau auxiliaire de même taille que le tableau donné en entrée par exemple).

Calcul de complexité d’un algorithme :

apparition d’un nombre dans un tableau. Soit $T$ un tableau de taille $N$ contenant des nombres entiers de $1$ à $k$ . Soit $a$ un entier entre $1$ et $k$ . La fonction suivante renvoie $1$ lorsque l’un des éléments du tableau est égal à $a$ , et $0$ sinon.

int Trouve (int T[], int n, int a)
{
    int i = 0 ;
    while (i \le n)
        if (T[i] == a )
            return i ;
    /* i == n ; le tableau est parcouru */
    return 0 ;
}

Cas le pire : $N$ (le tableau ne contient pas $a$ ) Cas le meilleur : $1$ (le premier élément du tableau est $a$ ) Complexité moyenne : Si les nombres entiers de $1$ à $k$ apparaissent de manière équiprobable, on peut montrer que le coût moyen de l’algorithme est

$N = k (1 - (1 - 1/k) )$

De fait les cas où l’on peut explicitement calculer la complexité en moyenne sont rares. Cette étude est un domaine à part entière de l’algorithmique

Analyse asymptotique

Analyse du temps d’un calcul d’un programme
- Valeur approchée Le temps de calcul d’un programme dépend trop de la vitesse de l’ordinateur et du compilateur utilisés. On peut donc calculer les performances d’un algorithme à facteur multiplicatif constant. Des programmes de complexités $n$ , $2n$ ou $3n$ sont quasiment équivalents.
- Règle des 90/10 : 90% du temps de calcul d’un programme est réalisé dans 10% du code. Inutile donc d’essayer de perdre trop de temps à optimiser les 90% qui ne prennent que 10% du temps. Autant se consacrer à ce qui est le plus pénalisant.
- Exemple : comparaisons d’un algorithme $A$ de complexité $100 n$ et d’un algorithme $B$ de complexité $2n^{2}$ (cf Aho-Ullman)
Notations et :
- Définitions. On dit que $f=\theta(g)$ lorsqu’il existe deux constantes $c_{1}$ et $c_{2}$ positives ( $f$ et $g$ sont également supposées à valeurs positives) telle que, pour $n$ assez grand $c_{1}.g(n) < f(n) < c_{2}.g(n)$ Remarquons que cette relation est réflexive.
- On dit que $f=O(g)$ lorsqu’il existe une constante $c$ positive telles que, pour n assez grand $f(n) < c.g(n)$ c’est dire que $f$ est bornée par $g$ à un facteur multiplicatif près.Cette relation n’est pas réflexive.
- Propriétés.Un polynôme est de l’ordre de son degré. On distingue les fonctions linéaires (en $O(n)$ ), les fonctions quadratiques (en $O(n^{2})$ ) et les fonctions cubiques (en $O(n^{3})$ ).Les fonctions d’ordre exponentiel sont les fonctions en $O(a^{n})$ ou $a >1$ .Les fonctions d’ordre logarithmique sont les fonctions en $O(\log(n)$ ) (Remarquons que peu importe la base du logarithme).
- Une classe intéressante d’algorithme est en $n \log(n)$ . Comparaison de $n \log(n)$ et de $n^{2}$ .
- Comparaison des asymptotiques classiques.
  - Rappelons que $log(n)^{i} \ll n^{k} \ll a^{n} \left( f\ll g \; \text{lorsque limite}\left(\dfrac{g}{f}\right) = 0\right)$ .
  - Fractions rationnelles
  - Factorielle : formule de Stirling
  - Nombres de Fibonacci
- Calcul de complexité dans les structures de contrôle.
  - Les instructions élémentaires (affectations, comparaisons) sont en temps constant, soit en $O(1)$ .
  - Tests : $O(\text{\tiny if A then B else C fi}) = O(A)+\text{max}(O(B),O(C))$
  - Boucles $O(\text{\tiny for i from 1 to n do Ai od}) = \text{somme}(O(Ai))$ . Lorsque $O(Ai)$ est constant à $O(A)$ , on a $O(\text{\tiny for i from 1 to n do A od}) = nO(A)$
  - Cas particuliers : boucles imbriquées
    - $O(\text{for i from 1 to n do for j from 1 to n do A od}) = n^2 O(A)$
    - Le fait que la borne sup de la boucle intérieure soit $i$ plutôt que $n$ ne change rien : $O(\text{for i from 1 to n do for j from 1 to i do A od od} ) = (1+2+...+n). O(A)$ .