Loading [MathJax]/jax/output/HTML-CSS/fonts/STIX-Web/fontdata.js

Complexité d'un algorithme

I : Introduction

L'analyse de la complexité d'un algorithme consiste en l'étude de la «quantité de ressources nécessaire» à l'exécution de cet algorithme. On distingue pour cela :

  • les ressources en temps : la «quantité de ressources nécessaire» est alors le nombre d'étapes de calcul,

  • les ressources en espace : la «quantité de ressources nécessaire» est alors le nombre de cases mémoire utilisées.

En NSI, nous nous intéresserons essentiellement à la complexité en temps.

I.1 : Un premier exemple

Supposons que le problème posé soit de trouver un nom dans un annuaire téléphonique qui consiste en une liste triée alphabétiquement de $30 \ 000$ noms. On peut s'y prendre de plusieurs façons différentes. En voici deux :

  • Recherche linéaire : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherché.
  • Recherche dichotomique : ouvrir l'annuaire au milieu, si le nom qui s'y trouve est plus loin alphabétiquement que le nom cherché, regarder avant, sinon, regarder après. Refaire l'opération qui consiste à couper les demi-annuaires (puis les quarts d'annuaires, puis les huitièmes d'annuaires, etc.) jusqu'à trouver le nom cherché.

Pour chacune de ces méthodes il existe un pire des cas et un meilleur des cas :

Recherche linéaire :

  • Le meilleur des cas est celui où le nom est le premier dans l'annuaire, le nom est alors trouvé dès la première étape de l'algorithme.
  • Le pire des cas est celui où le nom est le dernier dans l'annuaire, le nom est alors trouvé après avoir parcouru les $30 \ 000$ noms, soit $30 \ 000$ étapes.

Recherche dichotomique :

  • Le meilleur des cas est celui où le nom est situé au milieu de l'annuaire, le nom est alors trouvé dès la première étape de l'algorithme.
  • Le pire des cas est celiu où il faut séparer en deux l'annuaire, puis séparer à nouveau cette sous-partie en deux, ainsi de suite jusqu'à n'avoir qu'un seul nom. Le nombre d'étapes nécessaire sera alors $\log_2(30 \ 000) \approx 15$.

Sur cet exemple nous avons étudié la complexité de deux algorithmes dans le meilleur des cas et dans le pire des cas. Les informaticiens étudient aussi la complexité «en moyenne», c'est à dire en analysant la complexité «moyenne» pour un grand nombre de cas différents choisis aléatoirement.

En NSI, nous nous intéresserons essentiellement à la complexité dans le pire des cas.

I.2 : Complexité en temps dans le pire des cas

La complexité en temps est une mesure du temps utilisé par un algorithme. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Pour un même algorithme, ce nombre d'étapes peut varier en fonction de la taille des entrées. Ainsi pour les deux algorithmes l'exemple précédent, le nombre d'étapes dans le pire des cas est différent si la liste de noms comporte $n = 30 \ 000$ noms ou si la liste de noms en comporte $n = 500 \ 000$.

  • Recherche linéaire : la complexité dans le pire des cas est proportionnelle au nombre $n$ de noms dans la liste. On dit que la complexité est en $\mathcal{O}(n)$.

  • Recherche dichotomique : la complexité dans le pire des cas est proportionnelle au logarithme du nombre $n$ de noms dans la liste. On dit que la complexité est en $\mathcal{O}(\log_2(n))$

La notation $\mathcal{O}(...)$ nous servira désormais pour indiquer quelle est la complexité d'une instruction ou d'une séquence d'instructions. Cette notation indique que la complexité est proportionnelle à ce qui est indiqué entre parenthèses.

I.3 : Qu'est-ce qu'une «étape» de calcul ?

Nous avons dit que la complexité en temps compte le nombre d'étapes de calcul. Mais qu'est-ce qu'une «étape» de calcul ?

Il y a plusieurs façons de définir ces étapes, par exemple le nombre d'opérations dans une machine RAM, ou des mesures plus théoriques comme le nombre de comparaisons dans le cas d'un algorithme de tri ou le nombre de pas d'une machine de Turing.

Plus généralement, ce que l'on entend par «étape» de calcul est une instruction ou une séquence d'instructions qui prend un temps constant pour être exécutée, indépendamment de la taille de l'entrée de l'algorithme.

Dit autrement, une «étape» de calcul est une instruction ou une séquence d'instructions dont la complexité ne dépend pas de la taille $n$ de l'entrée, c'est à dire dont la complexité est constante, c'est à dire dont la complexité est en $\mathcal{O}(1)$.

Voici quatre exemples d'instructions ou séquences d'instructions dont la complexité est en $\mathcal{O}(1)$ et qui sont donc des «étapes» de calcul :

  • effectuer l'affectation de variable a = 2*6
  • effectuer l'affectation de variable a = (2*7+3)//(3*9-1) + (7-4)**2 + (7+4)**3
  • modifier la valeur d'une case d'un tableau tab[142] = 17984
  • effectuer une comparaison a <= 43

Attention toutefois, certaines instructions qui semblent être des «étapes» de calcul de complexité $\mathcal{O}(1)$ n'en sont pas. Par exemple en Python, insérer un élement en tête d'un tableau tab.insert(0, 74) a une complexité en $\mathcal{O}(n)$ où $n$ est la taille du tableau tab (en effet cette instruction demande de décaler toutes les $n$ valeurs du tableau vers la droite, soit $n$ étapes de calcul).

Une «étape» de calcul sera désormais une instruction ou une séquence d'instructions dont la complexité est en $\mathcal{O}(1)$, c'est à dire qui s'exécute en un nombre d'étapes constant.

II : Calculs de complexité

II.1 : Les règles de calcul

Les calculs de complexité sont basés sur quelques règles simples :

  • Règle 1 : effectuer successivement deux instructions ou deux séquences d'instructions de complexité $\mathcal{O}(f(n))$ conduit à une complexité en $\mathcal{O}(f(n))$,
  • Règle 2 : effectuer $n$ fois une instruction ou une séquence d'instruction de complexité $\mathcal{O}(f(n))$ conduit à une complexité en $\mathcal{O}(n \times f(n))$,
  • Règle 3 : effectuer successivement deux instructions ou séquences d'instructions de complexité $\mathcal{O}(f(n))$ et $\mathcal{O}(g(n))$ conduit à une complexité en $\mathcal{O}(h(n))$ où $h$ est la plus complexe des deux complexités parmi $f$ et $g$.

La règle 1 se justifie par le fait que :

  • puisque la première instruction est de complexité $\mathcal{O}(f(n))$, son nombre d'«étapes» est proportionnel à $f(n)$, c'est à dire de la forme $a \times f(n)$ ;
  • puisque la seconde instruction est de complexité $\mathcal{O}(f(n))$, son nombre d'«étapes» est proportionnel à $f(n)$, c'est à dire de la forme $b \times f(n)$ ;
  • par conséquent les deux instructions ou séquences d'instructions effectuées successivement ont un nombre d'«étapes» de la forme $a \times f(n) + b \times f(n) = (a+b) \times f(n)$, donc proportionnel à $f(n)$, c'est à dire de complexité $\mathcal{O}(f(n))$.

La règle 2 est évidente.

La règle 3 se justifie en effectuant un raisonnement comme pour la règle 1, mais en écrivant que le nombre d'étapes est «moins que proportionnel à $h(n)$».

II.2 : Un premier exemple : algorithme de la recherche du maximum dans un tableau

On note $n$ la taille du tableau non vide d'entiers passé en paramètre à l'algorithme. On peut analyser la complexité en commençant par les commentaires ci-dessous :

Entrée[ ]:
Entrée[ ]:

D'après la règle 1, on en déduit que la complexité d'un seul passage dans la boucle est en $\mathcal{O}(1)$.

D'après la règle 2, puisqu'on effectue $n$ passages dans la boucle, la complexité de la boucle est $\mathcal{O}(n \times 1) = \mathcal{O}(n)$.

D'après la règle 1, la complexité de la première instruction est en $\mathcal{O}(1)$.

Ce qui donne pour l'instant :

def maximum(tab):
    val_max = tab[0]                # O(1)
     
    for val in tab:                 # \
        if val > val_max:           #  } O(n)
            val_max = val           # /
            
    return val_max                  # O(1)

D'après le règle 3, la complexité de l'algorithme est en $\mathcal{O}(n)$ car la complexité en $\mathcal{O}(n)$ est plus complexe que celles en $\mathcal{O}(1)$.

Finalement, on en déduit que le nombre d'«étapes» nécessaire à l'exécution de cet algorithme est - pour de grands tableaux - proportionnel à la taille du tableau. On peut le constater en chronométrant l'algorithme sur trois grands tableaux de tailles différentes :

Entrée[ ]:

Utilisons la fonction chronometrer pour chronométrer notre algorithme :

Entrée[ ]:
Entrée[ ]:

On remarque qu'approximativement on a : temps_2 = 2 * temps_1 et temps_3 = 3 * temps_1 car les tableaux tab_2 et tab_3 sont respectivement deux et trois fois plus grands que tab_1 :

Entrée[ ]:
Entrée[ ]:

II.3 : Un second exemple : algorithme de la recherche d'un élément dans un tableau

On note $n$ la taille du tableau non vide d'entiers passé en paramètre à l'algorithme. On peut analyser la complexité en commençant par les commentaires ci-dessous :

Entrée[ ]:
Entrée[ ]:

D'après la règle 1, on en déduit que la complexité d'un seul passage dans la boucle est en $\mathcal{O}(1)$.

D'après la règle 2, puisqu'on effectue au plus $n$ passages dans la boucle, la complexité de la boucle est dans le pire des cas $\mathcal{O}(n \times 1) = \mathcal{O}(n)$.

Ce qui donne pour l'instant :

def recherche(tab, element): 
    
    for val in tab:             # \
        if val == element:      #  } O(n)
            return True         # /
        
    return False                # renvoi : O(1)

D'après le règle 3, la complexité de l'algorithme est en $\mathcal{O}(n)$ car la complexité en $\mathcal{O}(n)$ est plus complexe que celle en $\mathcal{O}(1)$.

Finalement, on en déduit que dans le pire des cas le nombre d'«étapes» nécessaire à l'exécution de cet algorithme est - pour de grands tableaux - proportionnel à la taille du tableau.

Notons que le temps d'exécution de cet algorithme est très variable d'une fois à l'autre. En effet lorsque l'élément cherché est présent au début du tableau, le temps d'exécution est très court. Pour s'en rendre compte, il suffit d'exécuter plusieurs fois la cellule de code ci-dessous :

Entrée[ ]:

II.4 : Un troisième exemple : algorithme du décompte des éléments d'un tableau

On note $n$ la taille du tableau non vide d'entiers passé en paramètre à l'algorithme. On peut analyser la complexité en commençant par les commentaires ci-dessous :

Entrée[ ]:
Entrée[ ]:

D'après la règle 1, on en déduit que la complexité d'un seul passage dans la boucle est en $\mathcal{O}(1)$.

D'après la règle 2, puisqu'on effectue $n$ passages dans la boucle, la complexité de la boucle est $\mathcal{O}(n \times 1) = \mathcal{O}(n)$.

Ce qui donne pour l'instant :

def decompte(tab):
    dico = {}                           # O(1)
    
    for val in tab:                     # \
        if val in dico.keys():          #  \
            dico[val] = dico[val] + 1   #   } O(n)
        else:                           #  /
            dico[val] = 1               # /
            
    return dico                         # O(1)

D'après le règle 3, la complexité de l'algorithme est en $\mathcal{O}(n)$ car la complexité en $\mathcal{O}(n)$ est plus complexe que celles en $\mathcal{O}(1)$.

Finalement, on en déduit que le nombre d'«étapes» nécessaire à l'exécution de cet algorithme est - pour de grands tableaux - proportionnel à la taille du tableau.

Pour cet algorithme, il convient de remarquer quelque chose de surprenant : le test de la présence d'une clef dans un dictionnaire est en $\mathcal{O}(1)$. C'est effectivement surprenant car même si le dictionnaire devient de plus en plus gros au fur et à mesure qu'il se remplit, ce test reste en $\mathcal{O}(1)$ ; alors que pour un tableau la recherche d'un élément dans le tableau est en $\mathcal{O}(n)$. Ceci s'explique par l'implémentation des dictionnaires Python avec des tables de hachage (tables de hachage qui expliquent également pourquoi des containers mutables tels que des tableaux ne peuvent pas être utilisés comme clefs d'un dictionnaire).

On retiendra de cet exemple que le test d'existence d'une clef dans un dictionnaire a une complexité en $\mathcal{O}(1)$ ce qui est contre-intuitif mais s'explique par l'utilisation de tables de hachage (qui empêchent l'utilisation de clefs telles que des tableaux).

Résumé :

Pour un algorithme, la complexité en temps dans le pire des cas établit un lien entre :

  • d'une part la taille $n$ des données en entrée de l'algorithme (souvent la taille d'un tableau ou d'un dictionnaire),
  • d'autre part le nombre d'«étapes» nécessaire pour que l'algorithme se termine dans le pire des cas.

Cette complexité se note $\mathcal{O}(f(n))$ :

  • lorsque $f(n) = n$, le nombre d'«étapes» dans le pire des cas est proportionnel à $n$ (pour de grandes valeurs de $n$),
  • lorsque $f(n) = 1$, le nombre d'«étapes» dans le pire des cas est constant et ne dépend pas de $n$.

Pour calculer la complexité d'un algorithme, après avoir étudié la complexité de chacune des instructions élémentaires, on utilise les trois règles suivantes :

  • Règle 1 : effectuer successivement deux instructions ou deux séquences d'instructions de complexité $\mathcal{O}(f(n))$ conduit à une complexité en $\mathcal{O}(f(n))$,
  • Règle 2 : effectuer $n$ fois une instruction ou une séquence d'instruction de complexité $\mathcal{O}(f(n))$ conduit à une complexité en $\mathcal{O}(n \times f(n))$,
  • Règle 3 : effectuer successivement deux instructions ou séquences d'instructions de complexité $\mathcal{O}(f(n))$ et $\mathcal{O}(g(n))$ conduit à une complexité en $\mathcal{O}(h(n))$ où $h$ est la plus complexe des deux complexités parmi $f$ et $g$.

Pour étudier la complexité des instructions élémentaires, il faut savoir que le bon sens permet souvent de savoir s'il s'agit de complexité $\mathcal{O}(1)$ ou $\mathcal{O}(n)$ mais qu'il y a de nombreuses exceptions dès qu'on utilise des fonctions Python opérant sur des containers (list, dict, tuple, str etc.). Ces exceptions seront l'objet d'un paragraphe plus bas dans ce notebook.

III : Exercices

Exercice 1 :

On considère généralement (voir l'article sur l'érosion de Wikipédia) que l'érosion moyenne à la surface de la terre est de $0,05$ mm/an.

On s'intéresse à une île isolée au milieu d'un lac dont la hauteur par rapport à la surface du lac est de $200$ m lors d'une certaine année de référence. On admet que la hauteur de cette île diminue de $0,05$ mm/an. Soit $H_n$ la hauteur de cette île $n$ années après l'année de référence. On a donc :

  • $H_{0} = 200$
  • $H_{1} = 199,99995$
  • $H_{2} = 199,99990$
  • $H_{3} = 199,99985$
  • $H_{4} = 199,99980$
  • $ \ldots $
  • $H_n = 200 - 0,00005 \times n$

Les deux fonctions ci-dessous prennent en paramètre un entier $n \geq 0$ et renvoient la hauteur $H$ de la colline l'année $n$ (c'est à dire $n$ années après l'année de référence).

Déterminer la complexité de ces deux fonctions.

def hauteur_v1(n):
    h = 200
    for i in range(n):
        h = h - 0.00005
    return h


def hauteur_v2(n):
    h = 200 - n * 0.00005
    return h
Solution

Fonction hauteur_v1

On a tout d'abord cette première analyse : 

def hauteur_v1(n):
    h = 200                # affectation : O(1)
    
    for i in range(n):
        h = h - 0.00005    # soustraction puis affectation : O(1)
    
    return h               # renvoi : O(1)

Dans un second temps, en prenant en compte la boucle qui est exécutée n fois (règle n°2), on obtient :

def hauteur_v1(n):
    h = 200                # O(1)
    
    for i in range(n):     # la boucle est O(n)
        h = h - 0.00005    # (car O(n * 1) = O(n))
    
    return h               # O(1)

Finalement, compte-tenu de la règle n°3, on en déduit que cette fonction a une complexité en $\mathcal{O}(n)$.

Fonction hauteur_v2

On a tout d'abord cette première analyse : 

def hauteur_v2(n):
    h = 200 - n * 0.00005    # multiplication, soustraction et affectation : O(1)
    return h                 # renvoi : O(1)

Compte-tenu de la règle n°1, on en déduit que cette fonction a une complexité en $\mathcal{O}(1)$. Cette implémentation hauteur_v2 est donc moins complexe que hauteur_v1.

Exercice 2 :

Dans cet exercice la complexité sera exprimée en fonction de $n$, taille du tableau tab.

Question 1 :

La fonction comptage ci-dessous prend en paramètres un tableau d'entiers tab ainsi qu'un nombre entier k ; et renvoie le nombre d'occurences de l'entier k dans le tableau tab.

def comptage(tab, k):
    compteur = 0
    for val in tab:
        if val == k:
            compteur = compteur + 1
    return compteur

Déterminer sa complexité.

Solution

On a tout d'abord cette première analyse : 

def comptage(tab, k):
    compteur = 0                         # affectation : O(1)
    
    for val in tab:            
        if val == k:                     # test d'égalité : O(1)
            compteur = compteur + 1      # somme et affectation : O(1)
    
    return compteur                      # renvoi : O(1)

Dans un second temps, en prenant en compte la boucle qui est exécutée n fois (règle n°2), on obtient :

def comptage(tab, k):
    compteur = 0                         # O(1)
    
    for val in tab:                      # \
        if val == k:                     #  } O(n) (car O(n * 1) = O(n))
            compteur = compteur + 1      # /
    
    return compteur                      # O(1)

Finalement, compte-tenu de la règle n°3, on en déduit que cette fonction a une complexité en $\mathcal{O}(n)$.

Question 2 :

La fonction doublon_v1 ci-dessous prend en paramètre un tableau d'entiers tab ; et renvoie True si tab contient au moins un doublon (c'est à dire contient au moins deux fois la même valeur) et False sinon.

def doublon_v1(tab):
    for val in tab:
        if comptage(tab, val) >= 2:
            return True
    return False

Déterminer sa complexité dans le pire des cas puis dans le meilleur des cas.

Solution

On a tout d'abord cette première analyse : 

def doublon_v1(tab):
    
    for val in tab:
        if comptage(tab, val) >= 2:      # appel à comptage et test de comparaison : O(n) et O(1)
            return True             # renvoi : O(1)
    
    return False                    # renvoi : O(1)

Dans un second temps, en prenant en compte la règle n°3, on obtient :

def doublon_v1(tab):
    
    for val in tab:
        if comptage(tab, val) >= 2:      # O(n)
            return True             # O(1)
    
    return False                    # O(1)

Dans un troisième temps et d'après la règle n°2, en prenant en compte la boucle qui dans le pire des cas est exécutée n fois, on obtient :

def doublon_v1(tab):
    
    for val in tab:                 # \
        if comptage(tab, val) >= 2:      #  } O(n**2) (car O(n*n) = O(n**2)
            return True             # /
    
    return False                    # O(1)

Finalement, compte-tenu de la règle n°3, on en déduit que cette fonction a une complexité dans le pire des cas en $\mathcal{O}(n^{2})$ ce qui est assez mauvais.


Et dans le meilleur des cas on passe une seule fois dans la boucle (lorsque la première valeur du tableau est un doublon) : on a alors une complexité en $\mathcal{O}(n)$ (en appliquant la règle n°3).

Question 3 :

La fonction doublon_v2 ci-dessous prend également en paramètre un tableau d'entiers tab ; et renvoie également True si tab contient au moins un doublon (c'est à dire contient au moins deux fois la même valeur) et False sinon.

Pour cela elle utilise la fonction decompte rencontrée au II.4 et dont la complexité est $\mathcal{O}(n)$.

def doublon_v2(tab):
    dico = decompte(tab)
    for val in dico.values():
        if val >= 2:
            return True
    return False

Déterminer sa complexité dans le pire des cas puis dans le meilleur des cas.

Solution

On a tout d'abord cette première analyse : 

def doublon_v2(tab):
    
    dico = decompte(tab)            # appel à la fonction decompte : O(n)
    
    for val in dico.values():
        if val >= 2:                # test de comparaison : O(1)
            return True             # renvoi : O(1) 
    
    return False                    # renvoi : O(1)

Dans un second temps d'après la règle n°2, en prenant en compte la boucle qui dans le pire des cas est exécutée n fois car le dictionnaire peut comporter autant de paires clef:valeur que d'éléments dans le dictionnaire, on obtient :

def doublon_v2(tab):
    
    dico = decompte(tab)            # O(n)
    
    for val in dico.values():       # \
        if val >= 2:                #  } O(n)
            return True             # / 
    
    return False                    # O(1)

Finalement, compte-tenu de la règle n°3, on en déduit que cette fonction doublon_v2 a une complexité dans le pire des cas en O(n) ce qui est meilleur que pour la fonction doublon_v1.


Et dans le meilleur des cas on passe une seule fois dans la boucle (lorsque la première valeur du dictionnaire prise en compte correspond à une clef qui est un doublon) : on a alors une complexité en O(n) (en appliquant la règle n°3).

Question 4 :

Vérifier expérimentalement les résultats des questions 2 et 3 en utilisant les tableaux aléatoires de taille $n$ générés par la fonction tableau_aleatoire(n) ci-dessous (un tableau renvoyé par cette fonction a une chance sur deux de contenir un doublon).

Entrée[ ]:
Entrée[ ]:
Entrée[ ]:
Entrée[ ]:
Solution

Il suffit d'exécuter dans trois cellules de code distinctes les instructions suivantes.

Cellule n°1 :

n = 100
t = tableau_aleatoire(n)

Cellule n°2 :

doublon_v1(t)

Cellule n°3 :

doublon_v2(t)


Avec n = 100 ou n = 1000, les appels aux fonctions doublon_v1 et doublon_v2 sont très rapides.

En revanche avec n = 10000 ou n=20000, les appels à la fonction doublon_v1 commencent à prendre beaucoup de temps ; alors que les appels à al fonction doublon_v2 restent très rapides.

Cela est lié au fait que la fonction doublon_v1 a une complexité moins performante (en $\mathcal{O}(n^{2})$) que doublon_v2 (en $\mathcal{O}(n)$).

IV : Des résultats de complexité à connaître

IV.1 : Opérations sur les tableaux et dictionnaires

Sur les tableaux
Opération Complexité en moyenne Remarques
len(tab) O(1)
val = tab[index] O(1)
tab[index] = val O(1)
tab.append(val) O(1)
tab.pop() O(1)
⚠️ tab.pop(index) O(n) Le coût dépend de l'endroit de la suppression
⚠️ tab.insert(index, val) O(n) Le coût dépend de l'endroit de l'insertion
⚠️ del tab[index] O(n) Le coût dépend de l'endroit de la suppression
val in tab O(n)
min(tab) O(n)
max(tab) O(n)
tab2 = copy(tab1) O(n)
tab3 = tab2 + tab1 O(k) k est la longueur de tab1
tab2.extend(tab1) O(k) k est la longueur de tab1
tab.sort() ou sorted(tab) O(n log(n) )
Sur les dictionnaires
Opération Complexité en moyenne Remarques
len(dico) O(1)
val = dico[clef] O(1)
dico[clef] = val O(1)
del dico[clef] O(1)
⚠️ clef in dico ou clef in dico.keys() O(1) Propriété qui justifie parfois l'utilisation de dictionnaires

IV.2 : algorithmes usuels

Algorithme Complexité Remarques
Recherche naïve O(n)
Recherche par dichotomie O(log(n)) nécessite un tableau trié
Maximum O(n)
Minimum O(n)
Somme ou Moyenne O(n)
Tri par insertion ou sélection O(n$^2$)
Tri fusion O(n log(n))

IV.3 : exemples de complexités

Complexité Dénomination n = 5 n = 10 n = 20 n = 50 n = 250 n = 1000 n = 10000 n = 1000000 Exemple
$O(1)$ constante 10 ns 10 ns 10 ns 10 ns 10 ns 10 ns 10 ns 10 ns accès à une cellule de tableau
$O(log(n))$ logarithmique 10 ns 10 ns 10 ns 20 ns 30 ns 30 ns 40 ns 60 ns recherche dichotomique
$O(\sqrt{n})$ racinaire 22 ns 32 ns 45 ns 71 ns 158 ns 316 ns 1 µs 10 µs test de primalité naïf
$O(n)$ linéaire 50 ns 100 ns 200 ns 500 ns 2.5 µs 10 µs 100 µs 10 ms parcours de liste
$O(n log(n))$ linéarithmique 40 ns 100 ns 260 ns 850 ns 6 µs 30 µs 400 µs 60 ms tri fusion
$O(n^{2})$ quadratique 250 ns 1 µs 4 µs 25 µs 625 µs 10 ms 1 s 2.8 h parcours de matrice, tri par insertion ou par sélection
$O(2^{n})$ exponentielle 320 ns 10 µs 10 ms 130 jours 10$^{59}$ ans Problème du sac à dos par force brute
$O(n!)$ factorielle 1.2 µs 36 ms 770 ans 10$^{48}$ ans Problème du voyageur de commerce avec une approche naïve

Il est important de connaître l'ordre croissant de ces complexités : constante, logarithmique, linéaire, linéarithmique, quadratique, exponentielle.

V : Questions de cours

Question 1 :

L'instruction instruction_3 est constituée de deux instructions :

  • instruction_1 de complexité $O(n)$,
  • instruction_2 également de complexité $O(n)$.

Quelle est la complexité de instruction_3 ?

Solution

Linéaire, c'est à dire $O(n)$ d'après la règle n°1.

Question 2 :

L'instruction instruction_3 est constituée de deux instructions :

  • instruction_1 de complexité $O(n)$,
  • instruction_2 également de complexité $O(n^{2})$.

Quelle est la complexité de instruction_3 ?

Solution

Quadratique, c'est à dire $O(n^{2})$ d'après la règle n°3.

Question 3 :

L'instruction instruction_3 est constituée d'une boucle qui exécute $log(n)$ fois une instruction de complexité $O(n)$.

Quelle est la complexité de instruction_3 ?

Solution

Linéarithmique c'est à dire $O(log(n)*n)$ d'après la règle n°2.

Question 4 :

Un algorithme de complexité $O(n)$ est exécuté en $20$ ms sur un tableau de taille $5000$.

Quel sera approximativement son temps d'exécution sur un tableau de taille $1 \ 000 \ 000$ ?

Solution

La taille du tableau $n$ est multipliée par $200$. Donc le temps de calcul va être multiplié approximativement par $200$, ce qui donne $20 * 200 = 4000 \ ms = 4 \ s$.

Question 5 :

Un algorithme de complexité $O(n^2)$ est exécuté en $20$ ms sur un tableau de taille $5000$.

Quel sera approximativement son temps d'exécution sur un tableau de taille $1 \ 000 \ 000$ ?

Solution

La taille du tableau $n$ est multipliée par $200$. Donc le temps de calcul va être multiplié approximativement par $200^{2}$, ce qui donne $20 * 200^{2} = 800000 \ ms = 800 \ s = 13 \ min \ 20 \ s$.

Question 6 :

Un algorithme de complexité $O(log(n))$ est exécuté en $20$ ms sur un tableau de taille $5000$.

Quel sera approximativement son temps d'exécution sur un tableau de taille $1 \ 000 \ 000$ ?

Solution

Puisque $log(5000) \approx 3.70$ correspond à $20 \ ms$. Alors $log(1000000) \approx 6.00$ correspondra à $\frac{6.00}{3.70} \times 20 \approx 32 \ ms$.


Remarque : ci-dessus a été utilisé le logarithme base 10 (celui des physicien·nes).
Mais si vous utilisez le logarithme népérien (celui des mathématicien·nes) vous trouverez $ln(5000) \approx 8.52$ et $ln(1000000) \approx 13.82$ qui conduiront également à $\frac{13.82}{8.52} \times 20 \approx 32 \ ms$.
Et si vous utilisez le logarithme base 2 (celui des informaticien·nes) vous trouverez $log_2(5000) \approx 12.29$ et $log_2(1000000) \approx 19.93$ qui conduiront également à $\frac{19.93}{12.29} \times 20 \approx 32 \ ms$.

Question 7 :

Pourquoi, en Python, évite-t-on d'insérer ou de supprimer des éléments situés à gauche d'un tableau ?

Solution

Parce que c'est une opération coûteuse de complexité $O(n)$ (en effet cette opération nécessite de «décaler d'un cran» toutes les valeurs suivantes dans le tableau).

Question 8 :

En Python, le test de présence d'une clef dans un dictionnaire est de complexité $O(1)$. Ce fait remarquable est lié à l'utilisation de tables de hachage. Néanmoins cela a un inconvénient concernant les clefs qui peuvent être utilisées dans un dictionnaire. Quel est cet inconvénient ?

Solution

On ne peut pas utiliser de containers mutables tels que les dictionnaires (dict) ou les tableaux (list).

Question 9 :

Donner la complexité dans le pire des cas de chacun de ces algorithmes, rencontrés en première NSI :

  • recherche naïve d'un élément dans un tableau non trié,
  • recherche du maximum ou minimum d'un tableau,
  • calcul de la somme des éléments d'un tableau d'entiers,
  • tri par insertion d'un tableau d'entiers,
  • tri par sélection d'un tableau d'entiers,
  • recherche par dichotomie d'un élément dans un tableau trié.
Solution
  • recherche naïve d'un élément dans un tableau non trié : $O(n)$,
  • recherche du maximum ou minimum d'un tableau : $O(n)$,
  • calcul de la somme des éléments d'un tableau d'entiers : $O(n)$,
  • tri par insertion d'un tableau d'entiers : $O(n^{2})$,
  • tri par sélection d'un tableau d'entiers : $O(n^{2})$,
  • recherche par dichotomie d'un élément dans un tableau trié : $O(log(n))$.