Calcul intuitif de complexités

Introduction

L'objectif de cet article est de vous présenter une approche intuitive de la notation $\small \cal O$ (lire "grand O") utilisée en algorithmique, qui est un indicateur de la complexité d'un algorithme, c'est à dire la façon dont il va évoluer en fonction des données d'entrée. Nous établirons quelques règles de calcul simples pour déterminer la complexité d'un algorithme sans passer par la définition mathématique des notations de Landau.

Nous allons parler de temps d'exécution des algorithmes (on parle de complexité temporelle) mais les notions suivantes peuvent aussi s'appliquer à l'occupation mémoire (on parle alors de complexité spatiale). Pour vous familiariser avec la notion de complexité temporelle, vous pouvez consulter l'Introduction au calcul de complexité en temps des algorithmes (cours de Mathias Hiron pour l'association France-IOI) en préambule à cet article.

L'analyse pessimiste

Une question incontournable lors de l'élaboration d'un algorithme est : sera-t-il possible d'exécuter cet algorithme sur une machine et d'obtenir un résultat en un temps raisonnable (ie. avant la fin du monde) ? Par exemple, un algorithme qui s'exécute en cinquante ans sur un ordinateur actuel ne présente que peu d'intérêt : même s'il calcule le bon résultat, il faudra attendre un temps déraisonnable avant d'en prendre connaissance. On a donc mis en place des outils de calcul pour évaluer le temps d'exécution d'un algorithme sans avoir à le tester. C'est l'un des rôles de la notation $\small \cal O$ : donner un ordre de grandeur du temps d'exécution d'un algorithme.

Mais il arrive aussi que l'algorithme s'exécute plus ou moins vite selon différents cas de figure de l'entrée. Par exemple, un algorithme de recherche linéaire dans un tableau retournera directement le résultat attendu si l'élément cherché est situé au début, mais devra parcourir tout le tableau si celui-ci est à la fin. Dans cette situation, on retiendra toujours le pire des cas. En effet, on a beau savoir qu'un programme s'exécute au mieux en deux secondes, cela n'est d'aucune utilité s'il lui faut au pire deux siècles avant de trouver le bon résultat ! Voilà un autre principe de la notation que nous allons découvrir : évaluer le temps d'exécution dans le pire des cas.

Enfin, le temps d'exécution exact d'un algorithme dépend de très nombreux paramètres : langage de programmation choisi, optimisations du compilateur, machine employée pour l'exécution, etc. Mais un calcul exact tenant compte de tous ces paramètres serait bien trop fastidieux : on cherchera donc un ordre de grandeur du temps d'exécution indépendamment des détails d'implémentation.

Ainsi, la notation $\small \cal O$ que nous allons découvrir permet de déterminer un ordre de grandeur du temps d'exécution d'un algorithme dans le pire des cas et indépendamment des conditions dans lesquelles on l'implémente.

Règles de calcul intuitif

Notre objectif sera dans un premier temps de déterminer des règles simples pour calculer rapidement la complexité d'un algorithme donné.

Facteurs constants

Nous allons partir du principe que chaque instruction élémentaire est exécutée en un certain temps, fixe, et donc que le temps d'exécution de notre algorithme dépend directement du nombre d'instructions élémentaires exécutées. Pour calculer la complexité d'un algorithme, nous allons donc partir du nombre d'instructions élémentaires et lui appliquer certaines règles de calcul.

En réalité, certaines instructions sont exécutées plus vite que d'autres, mais ce détail dépend de la machine que l'on utilise. Comme on cherche une expression indépendante des conditions d'utilisations, nous ramènerons à 1 toutes ces constantes. Plus généralement, on considérera que tous les facteurs constants dépendent de l'implémentation ou de la machine utilisée et non de l'algorithme lui-même, d'où notre premier principe :

Réduction des constantes : tous les facteurs constants sont ramenés à 1.

Considérons le pseudo-code suivant :

Fonction AfficherOrd(x)
    Soit y = 2 * x + 42
    Afficher y

Il comprend un nombre fixe d'instructions, le temps d'exécution du programme est donc une constante qui dépend des conditions d'utilisation. Sa complexité est donc $\small {\cal O}(1)$ de par le principe précédent. On dit qu'elle est en "grand O de 1".

Imaginons désormais une fonction chargée d'initialiser une liste de n éléments :

Fonction Initialiser(Liste)
    Pour chaque indice k de Liste
        Liste[k] = 42

Cette fonction exécute n affectations au total : une pour chaque élément de la liste. Le facteur n étant variable, on ne peut le ramener à 1 et la complexité de cet algorithme est donc $\small {\cal O}(n)$ .

On peut raisonner de même dans l'exemple suivant où T est un tableau de NxN cases :

Fonction InitialiserTableau2D(T, x)
    Pour x de 1 à N
        Pour y de 1 à N
            T[x][y] = x

La fonction exécute N.N = N² instructions, une pour chaque case du tableau. La complexité de l'algorithme est donc $\small {\cal O}(N^2)$ .

Addition

La notation $\small \cal O$ décrit l'évolution des performances de l'algorithme lorsque les paramètres d'entrée deviennent grands. Pour simplifier les calculs, on peut alors omettre dans une somme les termes qui sont négligeables devant d'autres termes quand les données d'entrée deviennent importantes.

Simplification des additions : un terme d'une somme négligeable devant un autre lorsque les paramètres d'entrée deviennent grands peut être omis.

Par exemple, considérons le programme suivant, qui utilise trois fonctions que nous avons définies :

Soit T un tableau 2D de NxN cases
Soit L une liste de N éléments
Initialiser(L)
AfficherOrd(L[0])
InitialiserTableau2D(T, L[0])

Les deux premières instructions sont des initialisations en temps constant, la complexité de cette partie est donc $\small {\cal O}(1)$ . L'appel à Initialiser est en $\small {\cal O}(N)$ tandis que celui à AfficherOrd est en $\small {\cal O}(1)$ et celui à InitialiserTableau2D en $\small {\cal O}(N^2)$ . La complexité du programme complet est donc : $\small {\cal O}(1 + N + 1 + N^2)$ .

Mais lorsque le paramètre N devient très grand, la valeur de N² est beaucoup plus grande que celle de N, qui est elle-même beaucoup plus importante que la constante 1. On peut donc appliquer la règle d'addition :

$\large {\cal O}(1\,+\,N\,+\,N^2)\,=\,{\cal O}(N\,+\,N^2)\,=\,{\cal O}(N^2)$

On peut appliquer cette règle de la même manière à des expressions moins simples :

$\large {\cal O}(n^8\,+\,n^4\,+\,8 n)\,=\,{\cal O}(n^8)$

Mais les complexités que l'on rencontre ne sont pas toujours des polynômes. Par exemple, les algorithmes de tri dichotomiques comme le tri fusion sont en $\small {\cal O}(n \ln n)$ pour des tableaux de longueur n. Considérons la fonction suivante :

Fonction TrouverNombreMins(tab)
    TriFusion(tab)
    Soit min = tab[0]
    Soit nbMins = 0
    Pour k de 1 à n
        Si tab[k] = min
            nbMins++
    Retourner nbMins

Celle-ci retourne le nombre d'éléments d'un tableau qui ont la valeur minimale. On connaît la complexité du tri fusion et celle de la simple boucle, d'où la complexité de l'algorithme complet :

$\large {\cal O}(n \ln n\,+\,1\,+\,n)\,=\,{\cal O}(n \ln n)$

En fait, il arrive souvent que l'on calcule comme ceci la complexité d'un algorithme complet à partir des complexités connues des différents algorithmes "élémentaires" qui le constituent (boucles, tris, recherches dichotomiques, etc.)

Vous pouvez simplifier l'expression suivante pour vous entraîner :

$\large {\cal O}(n!\,+\,3 n^2 \ln(n)\,+\,8)\,=\,?$

Le calcul de complexité de la fonction PeuOrthodoxe suivante est aussi laissé à titre d'exercice :

Fonction PeuOrthodoxe(Liste)
    Pour chaque indice k de Liste
        Pour chaque indice m de Liste
            Liste[k] = Liste[m]

Multiplication

Le principe des constantes s'applique aussi aux facteurs multiplicatifs, car eux aussi dépendent des conditions d'utilisation. Ainsi, on a :

$\large {\cal O}(8n^2\,+\,1000000n\,+\,93293923923)\,=\,{\cal O}(n^2)$

Mais il arrive aussi que les facteurs variables se multiplient à l'intérieur du $\small \cal O$ de la notation. Considérons la fonction suivante, qui prend en argument une liste de taille n et une fonction Fct :

Fonction ItérerListe(Lst, Fct)
    Pour chaque indice k de la liste Lst
        Fct(Lst[k])

Cet algorithme se contente d'appeler la fonction Fct sur chaque élément de la liste. Mais quelle est sa complexité ?

Tout dépend de la complexité de la fonction Fct. Si celle-ci est en temps constant, donc en $\small {\cal O}(1)$ , on exécutera n opérations de temps constants, et la complexité de notre appel sera en $\small {\cal O}(n)$ . Mais si Fct est en $\small {\cal O}(m^2)$ (où m est un autre paramètre variable) la complexité de l'appel à ItérerListe sera en $\small {\cal O}(n.m^2)$ .

Plus généralement, on voit que la complexité de ItérerListe correspond à celle de Fct multipliée par n. En fait, on pourrait dégager une règle de multiplication des complexités du type :

Multiplication des complexités : lorsqu'on remplace les opérations en temps constant d'un algorithme en $\small {\cal O}(f(n))$ par des appels à un algorithme en $\small {\cal O}(g(n))$ , la complexité obtenue est en $\small {\cal O}(f(n).g(n))$ .

Mais il est rare que l'on remplace toutes les opérations en temps constant par des appels à un autre algorithme. Pour pouvoir appliquer cette règle, il faudrait donc isoler la portion où l'on effectue l'appel, puis appliquer la règle des sommes pour remonter à la complexité globale. En pratique, il est plus simple de refaire le calcul de complexité du nouvel algorithme obtenu après insertion des appels.

Pratiquons sur quelques exemples, et d'abord sur la fonction suivante :

Fonction A1(n)
    Soit total = 0
    Pour k de 1 à n
        Afficher 42
        Pour l de 1 à n
            Pour m de 1 à n
                total += l + m + k
    Retourner total

Sa complexité est en $\small {\cal O}(n^3)$ . Maintenant, supposons que l'on ait une fonction F(n) en $\small {\cal O}(n)$ et considérons la fonction :

Fonction A2(n)
    Soit total = 0
    Pour k de 1 à n
        Afficher F(k)
        Pour l de 1 à n
            Pour m de 1 à n
                total += l + m + k
    Retourner total

L'appel à F(k) est en $\small {\cal O}(n)$ car k vaut au pire n. Comme les deux boucles imbriquées suivantes sont en $\small {\cal O}(n^2)$ la règle des sommes nous donne la même complexité globale :

$\large {\cal O}(n.(n\,+\,n^2))\,=\,{\cal O}(n^3)$

Considérons enfin la fonction A3 suivante :

Fonction A3(n)
    Soit total = 0
    Pour k de 1 à n
        Afficher 42
        Pour l de 1 à n
            Pour m de 1 à n
                total += F(l + m + k)
    Retourner total

Ici, la somme l + m + k vaut au pire 3n et l'appel à F(k + l + m) est donc en $\small {\cal O}(n)$ : comme il se situe au coeur des trois boucles imbriquées, et que l'opération Afficher 42 en $\small {\cal O}(1)$ est négligeable devant un $\small {\cal O}(n^3)$ , on a effectivement multiplication des complexités ; la complexité totale est donc :

$\large {\cal O}(n.(1\,+\,n^2.n))\,=\,{\cal O}(n^4)$

Lors de l'interaction entre deux algorithmes, il arrive donc que les complexités sur multiplient, mais ce n'est pas une généralité et il faut refaire à chaque fois le calcul détaillé.

Bilan

Les quelques règles simples que nous venons d'aborder permettent de calculer et de simplifier facilement des complexités polynomiales. Avec un peu de raisonnement, elles peuvent aussi aider à déterminer des complexités plus... Complexes (!) comme celles des algorithmes de tri dichotomiques.

Règles supplémentaires

Pour l'instant, nous n'avons considéré que des exemples assez simples sur lesquels les règles de calcul suffisent. Nous allons désormais voir quelques cas moins évidents qui nécessiteront l'emploi de nouvelles règles.

Complexités à plusieurs paramètres

Dans les exemples précédents, la complexité dépendait d'un unique paramètre que l'on pouvait identifier directement dans le code. En réalité, il arrive souvent qu'on ait plusieurs paramètres qui influent sur le temps d'exécution, comme par exemple les dimensions variables d'un tableau dont on parcourt toutes les cases.

Identification des paramètres : la complexité dépend de toutes les variables qui influent sur le temps de calcul.

Considérons par exemple une "carte", représentée en mémoire par un tableau 2D, et que l'on souhaite initialiser comme suit :

Fonction ParcourirCarte(carte)
    Soit L la largeur de la carte
    Soit H la hauteur de la carte
    Pour x de 1 à L
        Pour y de 1 à H
            Si carte[x][y] = 'X'
                Afficher "Trésor en (" + x + "," + y + ")"
    Pour d de 1 à min(L, H)
        Si carte[d][d] = 'X'
            Afficher "Trésor diagonal en " + d

On voit que le nombre d'instructions exécutées dépend des paramètres L et H, qui dépendent eux-mêmes directement de la carte en entrée. Ce sont donc des variables qui entrent dans le calcul de la complexité.

Le nombre d'instructions exécutées dans les deux boucles imbriquées est L.H (les tests sont des instructions conditionnelles élémentaires). La boucle suivante exécute $\small \min(L,H)$ instructions. La complexité est donc a priori $\small {\cal O}(LH + \min(L,H))$ .

Pour appliquer la règle de la somme, il faut considérer que tous les paramètres tendent vers l'infini. Dans ce cas, on a :

$\large \min(L,H)\ \leq\ L, H\ {\lt}\ L.H$

Ce qui nous donne la complexité de notre fonction :

$\large {\cal O}(LH\,+\,\min(L,H))\,=\,{\cal O}(LH)$

Mais il existe des cas où on ne peut pas simplifier la somme. Par exemple la fonction suivante :

Fonction TrifouillerCarte(carte)
    Soit L la largeur de la carte
    Soit H la hauteur de la carte
    Pour x de 1 à L
        carte[1][x] = '_'
    Pour y de 1 à H
        carte[1][y] = '#'

Sa complexité apparente est $\small {\cal O}(L + H)$ . Mais aucun des termes de la somme n'est négligeable devant l'autre : pour des cartes dégénérées (une seule ligne ou une seule colonne par exemple) on peut aussi bien avoir L grand devant H que H grand devant L. Cette forme est donc simplifiée au maximum, la complexité de cet algorithme est $\small {\cal O}(L + H)$ .

Détermination du pire cas

Parfois, les algorithmes étudiés comportent des grandeurs aléatoires, ou ne traitent qu'une partie variable des données. Par exemple, un algorithme de recherche du premier entier négatif d'un tableau qui examine tous les éléments du tableau peut très bien tomber sur le résultat dès la première case. Quelle est alors sa complexité ?

Loi de Murphy : la notation $\small \cal O$ décrit le comportement de l'algorithme dans le pire des cas possibles.

Ainsi, notre algorithme de recherche précédent est en $\small {\cal O}(n)$ où n est la longueur du tableau, parce que dans le pire des cas aucun élément n'est un entier négatif.

Considérons une autre opération sur notre "carte" en 2D :

Fonction BrouillerCarte(carte)
    Soit L la largeur de la carte
    Soit H la hauteur de la carte
    Pour l de 1 à L
        Soit R un nombre aléatoire entre 1 et H
        Pour c de 1 à R
            carte[c][l] = '_'

L'introduction d'une composante aléatoire pose un problème. Le salut réside dans les bornes : même si l'on ne connaît pas la valeur de l'entier R, on sait qu'il est compris entre 1 et H. Lors d'un passe dans la boucle de 1 à L, on exécute R instructions. Donc, dans le pire des cas, on exécute H instructions. Mais comme on cherche toujours le pire des cas de figures possibles, aussi improbable soit-il, on retrouve une complexité en $\small {\cal O}(LH)$ .

Conclusion

Voici un bref rappel des différentes règles que nous venons d'aborder :

Réduction des constantes : tous les facteurs constants sont ramenés à 1.
Simplification des additions : les termes d'une somme négligeables devant un autre peuvent être omis.
Identification des paramètres : la complexité dépend de toutes les variables qui influent sur le temps de calcul.
Loi de Murphy : la notation $\small \cal O$ décrit le comportement de l'algorithme dans le pire des cas possibles.

Celles-ci permettent de calculer intuitivement la complexité de bon nombre d'algorithmes. Vous pouvez aussi consulter les articles suivants sur le même sujet :

Introduction au calcul de complexité en temps des algorithmes : cours de Mathias Hiron pour France-IOI ;
An Introduction to Computational Complexity article plus général sur la complexité, en anglais ;
Approche théorique de la notation sur l'encyclopédie libre Wikipédia ;
Complexité algorithmique sur l'encyclopédie libre Wikipédia ;
Théorie de la complexité sur l'encyclopédie libre Wikipédia.