Initiation à la complexité algorithmique

Loin de moi l’idée de faire un article complet sur la notion de complexité, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur à la rentrée 2019), je me suis aperçu que cette notion allait pointer le bout de son petit museau perfide… Je voudrais donc par cet article familiariser les élèves avec elle.

C’est quoi la complexité d’un algorithme ?

C’est le nombre d’opérations et d’affectations faites. On appelle cela des opérations élémentaires. Prenons le programme Python suivant:

def convert(n):
    h = n // 3600
    m = (n - 3600*h) // 60
    s = n % 60
    return h,m,s

n = 102152

print("{} secondes = {} h {} min {} sec.".format(n,convert(n)[0],convert(n)[1],convert(n)[2]))

Dans la fonction “convert”, il y a :

• 3 affectations (h, m et s)
• 5 opérations (n//3600, 3600*h, n-3600*h, (n-3600*h)//60 et n%60)

La complexité de cette fonction est donc égale à 8.

Exercice 1

Montrer que la complexité de la fonction suivante est égale à 5.

def myFunction(n):
    if n%3 == 0:
        p = n/3 + 2
    else:
        p = n*2 + 1
    return p

Solution

il y a d’abord un test (if) dans lequel il y a une opération (n%3), ce qui nous fait pour le moment une complexité de 2.

Ensuite, quelle que soit l’issue du test, il y a 1 affectation (p) et 2 opérations (pour calculer p), soit une complexité augmentée de 3.

Au final, on obtient bien une complexité de 5.

Structures itératives

Dans un programme, il y a souvent des boucles. Nous allons voir un exemple avec une boucle “for”:

def recherche(l,x):
    for i in range(len(l)):
        if l[i]==x:
            return i
    return -1

l = "Bonjour."
x = "p"

print(recherche(l,x))

La fonction recherche a pour but d’afficher le rang où se trouve le caractère “x” dans la chaîne de caractères “l”, et affiche “-1” si ce dernier n’est pas trouvé.

• Au niveau de la boucle for, il y a 1 addition (sur i), une affectation (i) et une comparaison (test si i<len(l));
• dans la boucle for, il y a un test (if l[i]==x).

Au final, si n est la longueur de la chaîne de caractères, il y a 4n opérations élémentaires, qui correspond à la complexité de la fonction recherche.

Exercice 2

Calculer la complexité de la fonction somme définie dans ce programme:

def somme(n):
    s = 0
    for i in range(n+1):
        s += i
    return s

print(somme(100))

Solution

Il y a :

• au début, 1 affectation (s = 0);
• au niveau de la boucle for, 3 opérations élémentaires (affectation sur i, opération d’incrémentation sur i, test sur i);
• dans la boucle for, il y a 2 opérations élémentaires (1 affectation sur s et une opération sur s).

Ainsi, il y a 5 opérations élémentaires dans la boucle, répétées n fois, plus la première (hors boucle). La complexité de la fonction somme est donc égale à 5n+1.

En général, on appelle T la complexité (initiale de Time).

Exercice 3

Calculer la complexité de la fonction mystere du programme suivant:

def mystere(n):
    m = 0
    for i in range(n):
        for j in range(i):
            m += i+j
    return m

print(mystere(100))

Solution

• Il y a avant tout 1 affectation dès le début (m=0);
• ensuite, au niveau de la boucle sur i, 3 opérations élémentaires;
• au niveau de la boucle sur j, il y a 3 opérations élémentaires répétées i fois;
• dans la boucle sur j, il y a 3 opérations élémentaires (1 affectation sur m, une somme sur m et une somme de i et j).

Ainsi, à part la première affectation, il y a 9 opérations élémentaires pour chaque valeur de j possible. Il y a:

• 1 valeur possible de j quand i=0 (j=0);
• 1 valeur possible de j quand i=1 (j=0);
• 2 valeurs possibles de j pour i=2 (j=0 et j=1):
• etc.
• n-1 valeurs possibles de j pour i=n-1.

La complexité est donc égale à:$$\begin{aligned} & 1+9\times(1+1+2+3+\cdots+(n-1))\\=\ & 10+\frac{9n(n-1)}{2}\\=\ & \frac{1}{2}(9n^2-9n+20).\end{aligned}$$

Ordre de grandeur de la complexité

Nous le voyons dans l’exemple précédent, la complexité peut s’exprimer par un polynôme. Dans un tel cas, si n est relativement grand, on pourra assimiler la complexité à son ordre de grandeur. Par exemple ici, la complexité de la dernière fonction est de l’ordre de \(n^2\). On écrira alors:$$T_n=O(n^2).$$On dira ici que la complexité est quadratique.

Pour l’exercice 2, \(T_n=5n+1=O(n)\). On dira que la complexité est linéaire.

Fonction récursive

Une des fonctions récursives la plus simple est celle qui permet de calculer n! (la factorielle de n), c’est-à-dire \(2\times3\times\cdots\times n\).

def factorielle(n):
    if n == 0:
        return 1
    else:
        return n*factorielle(n-1)

Il y a un test pour commencer (sur n). Si le test est vrai, on s’arrête, sinon on effectue une opération (un produit) en faisant appel à la même fonction. Ainsi, si n est non nul, il y a 2 opérations élémentaires + le nombre d’opérations élémentaires de la fonction au rang n – 1.

Si \(T_n\) représente la complexité de la fonction factorielle(n) alors:$$T_n=T_{n-1}+2,\quad T_0=1.$$

La complexité est donc donnée par une suite arithmético-géométrique. C’est toujours le cas pour les fonctions récursives.

On peut alors montrer que \(T_n=2n+1=O(n).\)

Généralités

Si on considère une fonction toto(n) dans laquelle on fait appel à cette même fonction a fois et dans laquelle il y a b opérations élémentaires, si on note \(T_n\) sa complexité alors:$$T_n=aT_{n-1}+b.$$Ainsi, \(T_n=O(a^n)\). La complexité est alors exponentielle.

Exercice 4

Quelle est la complexité de la fonction suivante:

def fibo(n):
    if n<2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

Solution

Il y a 2 opérations élémentaires (un test sur n et une addition de fibo(n-1) et fibo(n-1)) donc:$$T_n=T_{n-1}+T_{n-2}+2,\quad T_0=T_1=1.$$ La complexité est donc une suite linéaire d’ordre 2 et d’équation caractéristique:$$r^2-r-1=0$$ de solutions \(r_1=\frac{1+\sqrt5}{2}\) et \(r_2=\frac{1-\sqrt5}{2}\). Comme \(|r_1|>|r_2|\), une propriété nous dit que la complexité de la fonction fibo(n) est:$$T_n=O(r_1^n).$$La complexité est alors exponentielle.