CM #4 : Complexité

Ce très court chapitre présente la complexité algorithmique et le vocabulaire associé. Quelques exemples sont présentés mais ce chapitre sert essentiellement de support à la suite du cours (notamment pour les tableaux, tris…).

Motivation

Étant donné que pour un programme ou sous-programme donné, il y a plusieurs façons de réaliser l’implémentation et que pour certains programmes (notamment dans le cas des systèmes embarqués) il y a des contraintes matérielles fortes, il est nécessaire d’évaluer les performances des algorithmes que l’on écrit. Cette notion de performance correspond à la complexité algorithmique où on cherche à estimer à l’avance:

le nombre d’opérations nécessaires pour que réaliser un sous-programme: complexité en temps
l’espace mémoire requis pour réaliser ce sous-programme: complexité en espace
les limites d’utilisation d’un sous-programme (i.e. savoir quand un sous-programme n’est plus performant comparé à un autre)

Pour cela, on évalue le nombres d’opérations élémentaires (affectations, additions, soustractions…, comparaisons…), le nombre d’itérations des boucles, le nombre de cases mémoires utilisées… La complexité d’un programme dépend souvent de variables d’entrée (valeurs demandées à l’utilisateurs, données mesurées…). En général, le calcul de complexité se fait sur:

la moyenne de toutes les exécutions possibles du programme
au mieux (i.e. l’exécution qui minimise la quantité que l’on mesure)
au pire (i.e. l’exécution qui minimise la quantité que l’on mesure)

on l’exprime également de manière asymptotique, c’est à dire comme une limite pour de grandes valeurs des paramètres d’entrées.

Exemples

Complexité constante

Soit la procédure suivante pour laquelle on cherche à mesurer la complexité en nombre de tests / comparaisons.

void print_max(int a, int b)
{
    int maxi;

    if (a < b)  maxi = b;
    else        maxi = a;
    printf("Le maximum de %d et %d est : %d\n", a, b, maxi);
}

Quelles que soient les valeurs de a et b, il n’y aura qu’une seule comparaison. Par conséquent la complexité en temps (où l’on mesure les tests) est en moyenne / au mieux / au pire de 1. L’expression asymptotique de cette complexité est $O(1)$.

Cas où le meilleur scénario est différent du pire scénario

Soit la fonction suivante pour laquelle on cherche à mesurer la complexité en nombre d’affectations.

int dummy(int n)
{
    int s = 0;
    if ( n > 0 )
    {
        for (int i = 0; i < n; i++)
        {
            s = s + 1;
        }
    }
    return s;
}

Ici on remarque que le meilleur des scénarios est atteint lorsque n est négatif ou nul puisque dans ce cas, il n’y a qu’une seule affectation (l’initialisation de s). A l’inverse si n est positif, il s’agit du pire scénario puisque l’on a n+2 affectations (initialisation de s puis n+1 itérations de boucles où il y a 1 affectation de s).

Complexité asymptotique

La complexité asymptotique est calculée pour des sous-programmes lorsque la valeur (ou l’évolution de la valeur) des paramètres d’entrées influe sur les performances de l’algorithme. Sur la fonction ci-dessous, la complexité en affectations et additions est linéaire (notation $O(n$)). En effet, pour un n quelconque, il y a n additions et n+1 affectations. Quand n devient très grand le n+1 est négligeable par rapport au n et par conséquent le coût en affectations et additions de cette fonction est proportionnel à n.

int sum(int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        s += i;
    }
    return sum;
}

Les complexités asymptotiques habituelles les plus fréquentes sont les suivantes:

$O(1)$: constante, indépendante des paramètres d’entrée
$O(n)$: linéaire en fonction des paramètres d’entrée
$O(n^2)$: quadratique en fonction des paramètres d’entrée
$O(P(n))$ où $P$ est un polynôme en fonction de n: polynomial en fonction des paramètres d’entrée
$O(2^n)$ exponentiel en fonction des paramètres d’entrée
$O(log(n))$ logarithmique en fonction des paramètres d’entrée

Le site big-O cheat sheet \cite{bigo} propose les complexités asymptotiques pour un grand nombre d’algorithmes courants.

Note

La notation O(x) est la plus souvent utilisée car elle permet de borner le temps maximum d'exécution de l'algorithme mais la complexité peut se déterminer de manière plus fine avec les notations suivantes:

o(N): complexité strictement inférieure à N
𝜃(N): complexité strictement égale à N
Ω(N): complexité strictement supérieure ou égale à N
ѡ(N): complexité strictement supérieure à N

A titre d’exemple, la fonction ci-dessous a une complexité quadratique (si on mesure le nombre d’opérations arithmétiques):

int dummy_func(int n)
{
    int s = 0;
    for (int i = 0; i < n; i++)
    {
        for ( int j = 0; j < n; j++)
        {
            s += i * j;
        }
    }
    return s;
}