Découpe en vidéos de Notion de complexité et grand O¶
Vidéo 1: Parlons d'efficacité d'un programme¶
Motivation¶
Montrer qu'une version d'un programme est plus efficace qu'une autre n'est, a priori, pas aisé. La succession ou l'imbrication des tests et des boucles et la multitude des possibilités fait qu'il n'est généralement pas possible ou raisonnable d'évaluer l'efficacité de l'algorithme pour chaque cas possible.
Critères de choix d'un algorithme¶
Généralement, il existe plusieurs méthodes pour résoudre un même problème. Il faut alors en choisir une et concevoir un algorithme pour cette méthode de telle sorte que cet algorithme satisfasse le mieux possible aux exigences.
Parmi les critères de sélection d'une méthode et en conséquence d'un algorithme, deux critères prédominent: la simplicité et l'efficacité de cet algorithme.
Si parfois ces critères vont de paire, bien souvent ils sont contradictoires; un algorithme efficace est, en effet, bien souvent compliqué et fait appel à des méthodes fort élaborées. Le concepteur doit alors choisir entre la simplicité et l'efficacité.
Si l'algorithme devra être mis en oeuvre sur un nombre limité de données qui ne demanderont qu'un nombre limité de calculs, cet algorithme doit de préférence être simple. En effet un algorithme simple est plus facile à concevoir et a moins de chance d'être erroné que ne le sera un algorithme complexe.
Si, par contre, un algorithme est fréquemment exécuté pour une masse importante de données, il doit être le plus efficace possible.
Au lieu de parler de l'efficacité d'un algorithme, on parlera généralement de la notion opposée, à savoir, de la complexité d'un algorithme.
La complexité d'un algorithme ou d'un programme peut être mesurée de diverses façons. Généralement, le temps d'exécution est la mesure principale de la complexité d'un algorithme.
D'autres mesures sont possibles dont:
- la quantité d'espace mémoire occupée par le programme et en particulier par ses variables;
- la quantité d'espace disque nécessaire pour que le programme s'exécute;
- la quantité d'information qui doit être transférée (par lecture ou écriture) entre le programme et les disques ou entre le programme et des serveurs externes via un réseau;
- ...
Nous n'allons pas ici considérer de programme qui échange un grand nombre d'informations avec des disques ou un autre ordinateur.
En général nous analyserons le temps d'exécution d'un programme pour évaluer sa complexité. La mesure de l'espace mémoire occupé par les variables sera un autre critère qui pourra être utilisé ici.
Nous verrons dans ce qui suit que, généralement, la complexité d'un algorithme est exprimée par une fonction qui dépend de la taille du problème à résoudre.
Vidéo 2: Approche pragmatique : mesurons le temps d'exécution¶
Une première approche pragmatique, pour avoir des informations sur le temps d'exécution, est tout simplement de le mesurer sur différents jeux de données.
Le module timeit permet de réaliser plusieurs exécutions d'un code donné et de retenir le meilleur temps CPU parmi l'ensemble des exécutions.
Les exécutions peuvent se faire au "terminal" ou dans un script ou une console Python
Par exemple dans un terminal l'instruction
python3 -m timeit -n 5 "print('coucou')"
mesure le temps d'exécution pris pour exécuter 5 fois le code donné en paramèrre.
$ python3 -m timeit -n 5 "print('coucou')"
coucou
...
coucou
coucou
5 loops, best of 5: 1.69 usec per loop
:0: UserWarning: The test results are likely unreliable. The worst time (9.01 usec) was more than four times slower than the best time (1.69 usec).
ThierryM:~ tmassart$
ou (ici à la console en utilisant le module timeit, un objet de classe Timer et la méthode timeit :
>>> import timeit
>>> t = timeit.Timer("print('coucou')")
>>> t.timeit(5)
coucou
coucou
coucou
coucou
coucou
4.3688996811397374e-05
Prenons un autre exemple : supposons qur nous désirions analyser les deux fonctions anagramme_dico(a, b) et anagramme_list(a, b) données ici, qui renvoient toutes deux True si les séquences a et b sont des permutations l'une de l'autre.
def anagramme_dico(a,b):
res = False
if len(a)==len(b):
dic_a = {}
dic_b = {}
for i in a:
dic_a[i] = dic_a.setdefault(i, 0) + 1
for i in b:
dic_b[i] = dic_b.setdefault(i, 0) + 1
res = dic_a == dic_b
return res
def anagramme_list(a,b):
res = False
if len(a) == len(b):
liste_b = list(b)
res = True
for i in a:
if i in liste_b:
liste_b.remove(i)
else:
res = False
return res
Prenons initalement la chaîne de 10 caractères dont on multiplie la longueur par deux à chaque itération, et donnons le temps d'exécution de chaque code.
import timeit
d1 = """
def anagramme_list(a,b):
res = False
if len(a) == len(b):
liste_b = list(b)
res = True
for i in a:
if i in liste_b:
liste_b.remove(i)
else:
res = False
return res
"""
d2 = """def anagramme_dico(a,b):
res = False
if len(a)==len(b):
dic_a = {}
dic_b = {}
for i in a:
dic_a[i] = dic_a.setdefault(i, 0) + 1
for i in b:
dic_b[i] = dic_b.setdefault(i, 0) + 1
res = dic_a == dic_b
return res
"""
taille = 1
for i in range(20):
t1 = timeit.Timer(d1 + f"""anagramme_list('RAVITAILLE'*{taille},'RAVITAILLE'[::-1]*{taille})""")
t2 = timeit.Timer(d2 + f"""anagramme_dico('RAVITAILLE'*{taille},'RAVITAILLE'[::-1]*{taille})""")
print(f"{taille*10:8d} {t1.timeit(1):11f} {t2.timeit(1):11f}")
taille *= 2
Celui-ci est presque immédiat pour les chaînes de taille inférieure à
100000 caractères. Au delà, la fonction anagramme_list prend un
temps de plus en plus significatif.
| Taille | anagramme_list (en s) | anagramme_dico (en s) |
|---|---|---|
| 10 | 0.000008 | 0.000006 |
| 20 | 0.000009 | 0.000009 |
| 40 | 0.000012 | 0.000012 |
| 80 | 0.000022 | 0.000021 |
| 160 | 0.000037 | 0.000037 |
| 320 | 0.000063 | 0.000074 |
| 640 | 0.000121 | 0.000145 |
| 1280 | 0.000261 | 0.000266 |
| 2560 | 0.000590 | 0.000571 |
| 5120 | 0.001676 | 0.001070 |
| 10240 | 0.005371 | 0.002035 |
| 20480 | 0.016907 | 0.003809 |
| 40960 | 0.098608 | 0.007899 |
| 81920 | 0.303143 | 0.012504 |
| 163840 | 1.231720 | 0.027419 |
| 327680 | 4.438462 | 0.050453 |
| 655360 | 20.400489 | 0.108817 |
| 1310720 | 102.657282 | 0.211423 |
| 2621440 | 586.517143 | 0.412746 |
| 5242880 | 2995.177226 | 0.991613 |
Par exemple dans la dernière ligne du tableau ici, pour une chaîne d'un peu plus de cinq millions de caractères, il faut approximativement 3000 secondes pour la version liste, soit près d'une heure, et moins d'une seconde pour la version dictionnaire.
On peut estimer grossièrement que le temps d'exécution grandit
- linéairement par rapport à la taille des séquences avec la fonction
anagramme_dico, et - de façon quadratique par rapport à la taille des séquences avec la fonction
anagramme_list
il est intuitivement normal que ces fonctions prennent un temps proportionnel
à la taille de a (on suppose que les deux chaînes de caractères sont de même taille).
Par contre, cette démarche est chronophage et on atteint vite ses limites car il n'est pas possible de faire des tests pour tous les exemples intéressants possibles et sur l'ensemble des ordinateurs possibles.
Vidéo 3: Approche analytique : comptons le nombre d'instructions¶
Essayons d'exprimer la complexité d'un algorithme par une fonction mathématique du nombre d'instructions élémentaires réalisées; celle-ci dépend de la taille du problème à résoudre.
Exemple: la recherche du minimum¶
Le travail nécessaire pour qu'un programme s'exécute dépend de la 'taille' du jeu de données fourni.
Par exemple, si nous analysons le code qui effectue une recherche du
minimum dans une liste Python s de petits entiers,
il est intuitivement normal que cet algorithme prenne un temps
proportionnel à len(s), et soit noté, par exemple, \(T(len(s))\).
Dénotons \(len(s) = n\). \(n\) est la taille de la liste et donc par extension, également la taille du problème.
Donnons ici la partie traitement de cet algorithme en
ayant eu soin de transformer le for en while pour mieux
détailler chaque étape d'exécution de l'algorithme et nous supposons n = len(s) connu dans le programme :
1 res = s[0]
2 i = 1
3 while i < n:
4 if s[i] < res:
5 res = s[i]
6 i = i + 1
7 return res
Pour obtenir des résultats qui restent valables quel que soit l'ordinateur utilisé, il faut réaliser des calculs simples donnant une approximation dans une unité qui soit indépendante du processeur utilisé. On peut, par exemple, faire l'approximation que chaque assignation de donnée simple ou test élémentaire représente une unité de temps d'exécution.
D'autres hypothèses auraient pu être faites. Par exemple, on aurait pu ne considérer que les assignations et rechercher la complexité en nombre d'assignations, ou ne considérer que les tests et rechercher la complexité en nombres de tests effectués par l'algorithme.
La complexité dépend donc fortement de l'unité prise qui doit être clairement précisée.
Avec nos hypothèses, les instructions des lignes 1, 2 et 7 prennent chacune une unité de temps d'exécution.
La boucle while de la ligne 3 à 6 s'exécute \(n-1\) fois, mais le test s'effectue \(n\) fois. La ligne 3 prend \(n\) unités et la ligne 6, \(n-1\) unités.
Le test de la ligne 4 prend une unité; il est effectué \(n-1\) fois et donc la ligne 4 utilisera au total \(n-1\) unités.
L'assignation de la ligne 5 prend une unité. Elle n'est effectuée que lorsque le test du if est vérifié.
Si l'on ne désire pas uniquement faire une seule mesure sur un jeu de
données bien précis, il faut donc expliciter si l'on désire connaître le temps
d'exécution dans le meilleur des cas \(T_{min}(n)\), le pire des cas \(T_{MAX}(n))\), ou
en moyenne \(T_{moyen}(n)\). Ici:
-
\(T_{min}(n)\) est donné dans le cas où le test du
ifn'est jamais vérifié, ce qui signifie que le minimum se trouve à la première composante. On a alors: \(T_{min}(n) = 1+1+n+(n-1)+(n-1)+1 = 3n+1\) -
\(T_{MAX}(n)\) est donné dans le cas où le test du
ifest à chaque fois vérifié, ce qui correspond au cas où toutes les valeurs dessont distinctes et triées en ordre décroissant. On a alors: \(T_{MAX}(n) = 1+1+n+(n-1)+(n-1)+(n-1)+1 = 4n\)
Le calcul de \(T_{moyen}(n)\) est généralement beaucoup plus difficile à effectuer. Si nous faisons des hypothèses simplificatrices que toutes les valeurs de la liste sont différentes et distribuées uniformément, nous obtenons :
\(3n+\ell n(n) < T_{moyen}(n) < 3n+\ell n(n)+1\)
Tout cela fait beaucoup de calculs juste pour 7 lignes de codes. Essayons de trouver plus simple !
Vidéo 4: La notion de grand \(O\)¶
Les exemples précédents montrent qu'il est souvent très difficile de calculer le temps moyen (ou maximal) d'exécution d'un algorithme. Ces calculs précis sont, de plus, inutiles puisqu'ils se basent sur des approximations grossières du temps d'exécution des actions élémentaires; évaluations qui ne tiennent pas non plus compte, par exemple, de l'ordinateur et de l'interpréteur utilisés.
Une évaluation du temps d'exécution d'un algorithme ne devient généralement intéressante que lorsque la taille du jeu de données, c'est-à-dire de \(n\) dans nos exemples précédents, est grande. En effet pour \(n\) petit, les algorithmes s'exécutent généralement très rapidement.
Supposons que la complexité maximale d'un algorithme \(A = 100.n\), que la complexité maximale d'un algorithme \(B = 15.n^2\) , celle de \(C = n^4\) et celle de \(D = 2^n\).
Le graphique montre qu'à partir de \(n\) valant quelques dizaines, \(2^n\) prend le pas sur \(n^4\) qui prend le pas sur \(15n^2\) et encore plus sur \(100n\)
La table suivante donne les valeurs de complexité pour \(n = 1,10,100,1,000, 10,000, 10^6\) et \(10^9\);
| \(n\) | \(A\) | \(B\) | \(C\) | \(D\) |
|---|---|---|---|---|
| \(1\) | \(100\) | \(15\) | \(1\) | \(2\) |
| \(10\) | \(1000\) | \(1500\) | \(10000\) | \(\approx 10^3\) |
| \(100\) | \(10000\) | \(150000\) | \(10^8\) | \(\approx 10^{30}\) |
| \(1000\) | \(100000\) | \(15.10^6\) | \(10^{12}\) | \(\approx 10^{300}\) |
| \(10000\) | \(10^6\) | \(15.10^8\) | \(10^{16}\) | \(\approx 10^{3000}\) |
| \(10^6\) | \(10^8\) | \(15.10^{12}\) | \(10^{24}\) | \(\approx 10^{300000}\) |
| \(10^9\) | \(10^{11}\) | \(15.10^{18}\) | \(10^{36}\) | \(\approx 10^{3.10^{8}}\) |
Valeur de \(100.n\), \(15.n^2\), \(n^4\) et \(2^n\) pour différentes valeurs de \(n\)
Ces valeurs doivent être divisées par le nombre d'instructions élémentaires par seconde pour obtenir un temps exprimé en seconde.
Les micro processeurs actuels permettent d'exécuter de l'ordre de \(10^9\) instructions par seconde soit environ \(10^{14}\) instructions par jour.
Cela signifie qu'en un jour, si aucune autre limitation ne perturbe l'exécution des algorithmes (telle que l'espace mémoire disponible par exemple), avec un microprocesseur, on peut résoudre avec l'algorithme
- \(A\) , un problème pour \(n\) valant approximativement \(10^{12}\)
- \(B\) , un problème pour \(n\) valant approximativement \(10^7\)
- \(C\) , un problème pour \(n\) valant approximativement \(3000\)
- \(D\) , un problème pour \(n\) valant approximativement \(50\)
et donc \(A\) est meilleur que \(B\), qui est meilleur que \(C\), lui-même étant meilleur que \(D\) (sauf pour de petites valeurs de \(n\)).
De façon générale, quand on regarde les complexités on voit un classement dans les fonctions n exposant n plus grand que 2 exposant n qui elle-même est plus grand que n exposant 3, plus grand que n exposant 2, plus grand que n log n plus grand que n plus grand que log de n plus grand que 1.
En vertu des remarques précédentes et de ces chiffres, on préfère donner un ordre de grandeur permettant d'avoir une idée du type d'algorithme en terme de complexité. Pour cela, on utilise la notation grand \(O\), qui permet:
- de déterminer si un algorithme a une chance de s'exécuter pour un \(n\) donné,
- connaissant le temps d'exécution pour un \(n\) donné, de faire une approximation de ce temps pour une autre valeur de \(n\).
Définition de complexité en O()¶
La notation grand \(O\) est définie comme suit:
Définition (\(O\)) : Une complexité \(T(n)\) est en \(O(f(n))\) si \(\exists N, c > 0 .\;\forall n > N \; T(n) \leq c.f(n)\)
Cette définition permet d'effectuer de nombreuses simplifications dans les calculs. En effet de cette définition il résulte que:
- Les facteurs constants ne sont pas importants. Par exemple que \(T(n)=n\) ou \(T(n)=100n\), \(T(n)\) est toujours en \(O(n)\)
-
Les termes d'ordres inférieurs sont négligeables. Ainsi si \(T(n) = n^3 + 4n^2 + 20n + 100\), on peut voir que pour \(n > N = 5\)
- \(n^3 > 4n^2\)
- \(n^3 > 20n\)
- \(n^3 > 100\)
et donc pour \(n>5\), \(T(n) = n^3 + 4n^2 + 20.n + 100 < 4n^3\).
De ce fait \(T(n)\) est en \(O(n^3)\).
Vidéo 5: Calcul du grand \(O\)¶
Classes de complexité¶
Si on peut calculer qu'un algorithme est un \(O(n^2 )\), il n'est pas intéressant, même si cela est trivialement vrai, d'exprimer le fait que \(T(n)\) est en \(O(n^3 )\), \(O(n^4 )\), ....
Lorsque l'on évalue le grand \(O\) d'une complexité, c'est la meilleure estimation "simple" que l'on cherche à obtenir.
Ainsi on classe généralement les complexités d'algorithmes selon leur grand \(O\) comme donné par la table suivante :
D'abord les code qui prennent un temps borné qui sont en \(O(1)\) complexité constant
ensuite les algorithmes de complexité logarithmique en \(O(log \, n)\) ensuite linéaires en \(O(n)\) ensuite
\(O(n \, log \, n)\)
ensuite les algorithmes à complexité polynomiales \(O(n^2 )\) : quadratique,
\(O(n^3 )\) , cubique, etc
Ensuite les complexités exponentielles avec \(O(2^n )\) , \(O(3^n )\) , ETC, \(O(n^n )\) , exponentiel en base n et ainsi de suite
Classes de complexité
Remarquons qu'en vertu du fait que pour tout a,b positif : \(log_a n = (log_a b).(log_b n)\)
et comme \(log_a b\) est une constante pour \(a\) et \(b\) fixés, si \(T(n)\) est en \(O(log_a n)\) il est également en \(O(log_b n)\). (la base du logarithme n'a donc pas d'importance pour exprimer un grand \(O\)). Notons encore que ceci n'est pas vrai pour la base des complexités exponentielles.
Règles de calcul du grand O¶
Donnons ici un petit nombre de règles permettant d'évaluer la complexité d'un algorithme. Ces règles ne donnent en général qu'une surapproximation parfois grossière; une estimation plus précise devant tenir compte du fonctionnement de l'algorithme.
Tout d'abord, l'évaluation se fait en "bottom-up", depuis les instructions simples, vers les instructions plus complexes. Si l'on regarde l'arbre syntaxique du code de la recherche du minimum, on détermine donc d'abord la complexité des feuilles (avec les instructions 1, 2, 5, 6 et 7) pour ensuite remonter en déterminant la complexité de l'instruction if et ensuite du while pour enfin avoir la complexité de tout le code qui correspond à la racine de l'arbre syntaxique.
1 res = s[0]
2 i = 1
3 while i < n :
4 if s[i] < res:
5 res = s[i]
6 i = i + 1
7 return res
Règle 1 (unité)
Il faut clairement définir l'unité utilisée et les éléments pris en compte. Ainsi, si l'on regarde la complexité en temps d'exécution et si l'on tient compte des tests élémentaires, des assignations, des lectures de données et des écritures de résultats, une assignation à une variable simple, une instruction input ou print d'une donnée simple, ou l'évaluation d'une expression (ou d'une condition) simple ne donnant pas lieu à l'exécution de fonctions, prend un temps constant fixé et est donc en \(O(1)\). L'assignation à des objets plus complexes ou des input ou print de données plus complexes peut ne plus être en \(O(1)\) en fonction de leur taille qui peut dépendre de la taille du problème (\(n\)).
Par exemple, en comptabilisant le temps de toutes les instructions, chacune des instructions suivantes est en O(1) :
x = 3.14
z = 3 ** 25 + x - 36
x == 3.14
print(3.14)
y = int(input()) (pour une petite valeur lue)
Règle 2 (séquence)
- Si un traitement 1 prend un temps \(T_1(n)\) qui est en \(O(f_1(n))\) et
- un traitement 2 prend un temps \(T_2(n)\) qui est en \(O(f_2(n))\) alors
- le traitement 1 suivi du traitement 2 prend \(T_1(n) + T_2(n)\) et est en \(O(f_1(n) + f_2(n)) = O (max(f_1(n) , f_2(n)))\)
où max prend la fonction qui croît le plus vite c'est-à-dire de plus grand ''ordre''.
Par exemple si \(T_1(n)\) est en \(O(n^2 )\) et \(T_2(n)\) est en \(O(n)\), \(T_1(n) + T_2(n)\) est en \(O(n^2 + n) = O(n^2)\)
En particulier une séquence d'instructions simples (dont on tient compte) ne faisant aucun appel à une procédure ou à une fonction ne dépend pas de \(n\) et sont donc en \(O(1)\).
Par exemple la séquence de toutes les instructions simples précédentes est en \(O(1)\).
Règle 3 (if)
Pour un
if condition: instruction_1 else: instruction_2où
instruction_1est en \(O(f_1(n))\)instruction_2est en \(O(f_2(n))\)- l'évaluation de la
conditionest en \(O(g(n))\)suivant le test, le
ifsera en \(O(max(f_1(n),g(n)))\) ou en \(O(max(f_2(n),g(n)))\) et peut être borné par: \(O(max(f_1(n), f_2(n), g(n)))\)
Notons que souvent \(g(n)\) est en \(O(1)\).
Par exemple le code suivant est en \(O(1)\)
a = int(input()) # O(1)
if (a > 100): # O(1)
print('a dépasse le centaine') # O(1)
else: # O(1)
print('a ne dépasse pas la centaine') # O(1)
Cette règle peut être généralisée pour une instruction if ayant une
ou des parties elif.
Règle 4 (while)
Pour un
while, sachant que - le corps de la boucle est en \(O(f_1(n))\) et que - l'évaluation de la condition est en \(O(f_2(n))\), - si on a une fonction en \(O(g(n))\) qui donne une borne supérieure du nombre de fois que le corps sera exécuté, alorsle
whileest en \(O(f(n).g(n))\) avec \(f(n) = max(f_1(n),f_2(n))\).
Par exemple, la fonction de recherche dans une liste s, de l'indice i de l'élément de s dont la composante \(s[i][0]\) vaut x en est \(O(n)\) où \(n\) est la taille de s(on suppose que les éléments de s sont des tuples.)
def recherche(s,x): # O(n)
"""Renvoie l'indice où se trouve la valeur x dans s.
None si x n'existe pas.
"""
i = 0 # O(1)
while i < len(s) and s[i][0] != x: # O(n) (cond en O(1), nb d'it en O(n))
i = i+1 # O(1)
if i == len(s) # O(1)
i = None # pas trouvé # O(1)
return i # O(1)
Règle 5 (for)
Pour une boucle
for, il suffit de ''traduire'' leforenwhile.
Donnons de simples exemples de complexité avec des for
for i in range(100):
print(i)
est en \(O(1)\) car le nombre d'itération est de \(100\) qui est en \(O(1)\).
Par contre, pour une liste s de taille \(n\) d'entiers (de petite valeur) où \(n\) est un paramètre qui dépend de la taille du problème :
for elem in s:
print(elem)
est en \(O(n)\).
Règle 6 (fonction)
L'appel à une fonction est en \(O(f(n))\) correspondant à la complexité du traitement de cette fonction pour les paramètres effectifs donnés.
Par exemple on peut voir que la complexité de la fonction ecrit_carre_nxn est en \(n^2\) où n est l'entier reçu en paramètre.
Si l'on appelle cette fonction avec la valeur taille ** 3 où taille est un entier lu, la complexité résultant de l'exécution est donc en \(O(taille^6)\) (soit \(O(n^2)\) pour \(n = taille^3\)).
def ecrit_carre_nxn(n): # complexité de la fonction O(n^2)
for i in range(n):
for j in range(n):
print('X', end='')
print()
taille = int(input()) # O(1)
ecrit_carre_nxn(taille**3) # carré de taille taille^3 # O((taille^3)^2) = O(taille^6)
On peut raffiner ces calculs, selon que l'on essaye de trouver une
complexité minimale, moyenne ou maximale. Ce raffinement se situera
dans le nombre de fois qu'une instruction sera répétée, ayant par
exemple certaines hypothèses sur la probabilité que certaines
conditions de if ou de boucles sont vérifiées.
Vidéo 6 : Application des règles de calcul¶
Note : Les algorithmes dont les codes python sont donnés ici sont expliqués dans le chapitre 8 du cours : http://di.ulb.ac.be/verif/tmassart/Prog/html/chapitre8.html#recherche-sequentielle
Ayant ces règles d'évaluation du grand \(O\) pour chaque type d'instruction, le calcul de la complexité d'un algorithme se fait en partant des complexités des instructions simples, et en calculant, de proche en proche, les complexités des instructions non simples à partir des résultats déjà calculés. Ces calculs procèdent en quelque sorte par des regroupements en suivant la structure de l'algorithme.
Complexité de la recherche du minimum¶
Prenons l'exemple de la recherche du minimum c'est-à-dire du
traitement suivant (après traduction en utilisant un while en ayant n = len(s):
1 res = s[0]
2 i = 1
3 while i < len(s):
4 if s[i] < res:
5 res = s[i]
6 i = i + 1
7 return res
Rappelons que le traitement, comme tout algorithme, peut être décomposé sous forme d'arbre syntaxique comme donné par la figure suivante où chaque noeud représente une instruction Python simple ou composée.
Décomposition d'un traitement en suivant la structure
Les noeuds sans fils, appelés les feuilles de l'arbre,
correspondant aux instructions 1,
2, 5, 6 et 7, représentent des instructions d'assignations simples ou
return qui, d'après la règle 1, sont en \(O(1)\).
De ce fait, d'après la règle 3, le noeud 4-5 correspondant à
l'instruction if est en \(O(1)\).
D'après la règle 2, la complexité de la séquence d'instructions 4-6 est en \(O(1)\).
On peut maintenant évaluer la complexité du while (noeud 3-6),
il s'exécute \(n-1\) fois et la complexité du corps de la boucle est,
comme on vient de le voir, en \(O(1)\). Donc d'après la règle 4, la
complexité du while est en \(O(n)\).
Finalement, d'après la règle 2, la complexité de tout le traitement est en \(O(1+1+n+1)\) qui peut être simplifié par \(O(n)\).
Note
-
Si, par exemple, un algorithme \(A\) est en \(O(n)\) et un algorithme \(B\) est en \(O(n^2 )\), \(A\) est 'meilleur', en terme, de complexité que \(B\).
Par contre si \(A\) et \(B\) sont tous les deux en \(O(f(n))\), il faut détailler le calcul de la complexité pour déterminer lequel est plus complexe que l'autre.
-
D'après la définition du \(O\), l'algorithme de recherche du minimum est en \(O(n)\) et donc trivialement également en \(O(n^2)\), \(O(n^3)\), ..., \(O(n^n)\). Lorsque l'on cherche la complexité d'un algorithme, on essaye bien évidemment de donner la valeur la plus précise (Exemple: \(O(n)\) pour la recherche du minimum)
-
Rappelons que l'on peut évaluer plusieurs complexités différentes. Par exemple, pour les algorithmes de tris de liste, on peut regarder la complexité en terme de nombre d'instructions ou seulement regarder les instructions qui effectuent des déplacements d'éléments (le déplacement d'un élément peut prendre beaucoup plus de temps que les autres instructions). Certains tris sont en \(O(n^2)\) si l'on regarde toutes les instructions, mais en \(O(n)\) en terme de déplacement d'informations.
Complexité de la recherche séquentielle et dichotomique¶
Il est facile de voir que l'algorithme de recherche séquentielle, vue plus haut, est
également en \(O(n)\) où \(n\) est la longueur de la liste et en supposant
que les tests s[i] == x sont effectués en \(O(1)\).
Recherche dichotomique
Une version Python de l'algorithme classique de recherche dichotomique de l'indice d'un élément dans un vecteur (une liste python) s est donné ici :
def recherche_dichotomique(s,x): # O(log n)
"""Renvoie un indice où se trouve la valeur de x dans s
None s'il n'existe pas.
La méthode de recherche dichotomique ou binaire est utilisée.
"""
bi, bs = 0, len(s) # O(1)
m = (bi+bs)//2 # O(1)
while bi < bs and x != s[m][0]: # O(log n) (O(log n) itérations)
m = (bi+bs)//2 # O(1)
if s[m][0] < x: # O(1)
bi = m+1 # O(1)
else: # O(1)
bs = m # x est avant ou est trouvé # O(1)
if len(s) <= m or s[m][0] != x: # pas trouvé # O(1)
m = None # O(1)
return m # O(1)
Attention, ici on suppose que chaque élément de s contient un couple avec la clé en sous composante 0 et une information satellite en sous composante 1. Ainsi s[m][0] représente la clé de l'élément d'indice m dans la liste et s[m]représente tout l'élément (clé et information satellite).
Pour calculer la complexité de la recherche dichotomique, en
utilisant les règles vues précédemment, on peut assez rapidement
observer que la complexité moyenne ou maximale en nombre d'actions
élémentaires de cet algorithme est en \(O(f(n))\) où \(f(n)\) est le
nombre respectivement moyen \((f_{moyen(n)})\) ou maximum \((f_{max(n)})\)
de fois que la boucle while est exécutée.
Pour évaluer \(f_{max(n)}\), commençons par analyser le comportement de
l'algorithme. Nous pouvons tout d'abord remarquer qu'à chaque tour de boucle,
au pire des cas, l'intervalle de recherche est divisé par deux, quelle que soit
la valeur de x.
La figure suivante donne une évolution possible de l'intervalle de
recherche dans s pour une liste à 100 éléments en supposant que x n'est
pas dans s mais que s[40] < x < s[41]
Evolution de l'intervalle de recherche lors d'une recherche dichotomique
Le while s'exécute donc au maximum 7 fois. De façon générale on peut
voir que:
\(2^{f_{max}(n)-1} \leq n < 2^{f_{max}(n)}\)
et donc que \(f_{max(n)} <= \log_2(n) + 1\)
La recherche dichotomique a donc une complexité maximale en \(O(ln \; n)\).
On peut calculer que la complexité moyenne (en supposant ou non que
x est dans s) est également en \(O(ln \; n)\).
Notons que dans la section algorithmique, nous verrons que cette complexité peut être calculée avec le master theorem (https://fr.wikipedia.org/wiki/Master_theorem) et la relation de récurrence \(T(n) = T(n/2) + O(1)\)
Vidéo 7 : complexité des tris simples¶
Complexité du tri par sélection¶
Soit une solution Python du tri par sélection :
def tri_selection(s): # O(n^2)
"""Trie la liste s par sélection."""
n = len(s) # O(1)
for i in range(n-1): # O(n^2) (O(n) itérations)
# recherche du min dans s[i..n]
min = i # min = indice du min provisoire # O(1)
for j in range(i+1,n): # O(n) (O(n) itérations)
if s[j][0] < s[min][0]: # O(1)
min = j # O(1)
# placement du ième élément: échange s[i]<->s[min]
s[min],s[i] = s[i],s[min] # O(1)
où l'on suppose ici aussi, le vecteur s composé de couples (clé, information satellite).
Pour calculer la complexité maximale du tri par sélection décomposons l'algorithme sous forme d'arbre en suivant sa structure; ceci est donné en figure suivante:
Décomposition du tri par sélection
En supposant que toutes les instructions et les traitements de passages de paramètres interviennent dans ce calcul, en suivant les règles pour calculer cette complexité, nous obtenons :
1, 5, 8, 11et13, sont en \(O(1)\)- le
if(10-11) est en \(O(1)\) - le
for(9-11) imbriqué est en \(O(n-i)\) et peut être borné par \(O(n)\) - le
forglobal (6-13) est en \(O(n^2)\) - la procédure
tri_selection(1-13) est en \(O(n^2)\)
Ce calcul peut être raffiné mais les résultats restent en \(O(n^2)\).
Complexité du tri par insertion¶
En analysant l'algorithme de tri par insertion, on peut voir que sa complexité maximale est également en \(O(n^2)\). On peut voir que la complexité minimale est rencontrée dans le cas où la liste est déjà triée et vaut \(O(n)\)
Complexité du tri par échange ou tri Bulle¶
Pour le tri par échangé, également appelé, tri bulle, la complexité maximale est également en \(O(n^2)\). Ici, la complexité minimale est aussi en \(O(n^2)\).
Complexité du tri par énumération¶
Soit une solution Python du tri par énumartion où l'on suppose les valeurs possibles en \(0\) et \(m - 1\) :
m = 5
def tri_enumeration(s):
"""Trie les n premières composantes de la liste s par énumération."""
n = len(s) # O(1)
w = [0]*n # O(n)
count = [-1]+[0]*(m-1) # O(m)
# 1 Comptage
for j in range(n): # O(n) (O(n) itérations)
count[s[j][0]] +=1 # O(1)
# 2 Cumul des compteurs
for i in range(1,m): # O(m) (O(m) itérations)
count[i] += count[i-1] # O(1)
# 3 Placement des éléments dans w
for j in range(n-1,-1,-1): # O(n) (O(n) itérations)
w[count[s[j][0]]] = s[j] # O(1)
count[s[j][0]] -= 1 # O(1)
# 4 Recopiage de w dans s
s[:] = w # O(n)
Si \(m < n\), la complexité moyenne et maximale de ce tri est en \(O(n)\) ce qui est remarquable.
Vidéo 8 : Complexité des manipulations de séquences de données python¶
La complexité des manipulation des séquences de données sont dépendantes de l'implémentation de python utilisée.
Nous nous basons donc sur l'implémentation CPython utilisé au moins jusqu'à la version Python 3.10.
Dans ce qui suit, on suppose que \(n\) est le nombre d'éléments dans la séquence et \(k\) la valeur (ex: longueur) du paramètre.
La complexité moyenne suppose que les paramètres sont générés uniformément de façon aléatoire.
Complexité des opérations sur les listes¶
De façon interne, une liste est représentée sous forme de vecteur où
les composantes sont contiguës en mémoire et avec, en moyenne, de la
place libre pour allonger la liste. La pire opération est donc une
insertion ou suppression en début de liste car toutes les composantes
doivent bouger. Malheureusement, au pire des cas, un simple
s.append(x) peut demander de recopier toute la liste s'il n'y a
plus de place libre juste après la liste s.
| Opération | Complexité moyenne | Complexité maximale |
|---|---|---|
| Copy | O(n) | O(n) |
| Append | O(1) | O(n) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Set Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(n+k) |
| Extend | O(k) | O(n+k) |
| Sort | O(n log n) | O(n log n) |
| Multiply | O(nk) | O(nk) |
| x in s | O(n) | O(n) |
| min(s), max(s) | O(n) | O(n) |
| len(s) | O(1) | O(1) |
Complexité des opérations sur les dictionnaires¶
Avec l'interpréteur que nous utilisons, un dictionnaire Python est stocké dans une table (zone mémoire contiguë).
Pour simplifier supposant que c'est une table à MAX composantes (par exemple pour un petit dictionnaire MAX = 100.
L'accès à une composante du dictionnaire (Get Item) se fait par hashing (hash(cle) % 100) qui calcule un indice entre 0 et MAX-1.
En moyenne cet indice correspond à l'emplacement dans la table où l'élément (clé et valeur) va être stocké.
Cette opération (hashing, modulo et accès à la table) prend un temps constant O(1).
La complexité moyenne suppose que les collisions sont rares avec la fonction de hashage (ce qui est généralement la cas).
Le cas moyen suppose que les paramètres sont choisis uniformément aléatoirement parmi les clés possibles.
Malheureusement, il peut y avoir des collisions. Au pire des cas,
pour un dictionnaire de néléments, l'accès à un élément aura
n-1 collisions plus le dernier hashing et prend un temps (complexité maximale) en
O(n).
En terme de complexité, placer un élément (Set Item) revient à y accéder suivit du stockage de l'élément qui est en O(1) en moyenne et O(n) en complexité maximale, soit la même complexité que l'accès à un élément.
| Opération | Complexité moyenne | Complexité maximale |
|---|---|---|
| Copy | O(n) | O(n) |
| Get Item | O(1) | O(n) |
| Set Item | O(1) | O(n) |
| Delete Item | O(1) | O(n) |
| Iteration | O(n) | O(n) |