CPGE Oujda                                                                                                                                              Spé

Initiation à la Complexité algorithmique

Étudier la complexité (en temps) d’une fonction f , c’est déterminer son temps d’exécution Tf   en fonction de la taille des données. En pratique :

•  Ce temps d’exécution est compté en nombre d’opérations élémentaires (à préciser

suivant les cas) ;

•  La taille des données est également à préciser, pour une liste L c’est sa longueur ;

•  On se contente d’un ordre de grandeur en utilisant la notation O.

L’intérêt de pouvoir comparer la complexité de différents  algorithmes c’est pour ne conserver que les plus efficaces. Prenons par exemple l'algorithme qui lit un tableau et teste chacune de ses cases : si le tableau a n cases, l'algorithme effectuera n tests ! On dit que sa complexité est en O(n).

Le grand O

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 du compilateur ou de l’interpréteur utilisés.

Définition (O) : Une complexité T(n) est dite en grand O de f(n) (en O(f(n)) s’il existe un entier N et une constante c > 0 tels que pour tout entier n > N nous avons T(n) <= 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. En effet, si par exemple T(n)=n ou si 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

o    n^3 > 4n^2

o    n^3 > 20n

o    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).

Classes de complexité

Règles de calcul du grand O

Règle 1 (unité)

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

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)

Règle 3 (if)

Pour un if condition: instruction_1 else: instruction_2

• instruction_1 est en O(f_1(n))
• instruction_2 est en O(f_2(n))
• l’évaluation de la condition est en O(g(n))

suivant le test, le if sera 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)))

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é, alors le while est en O(f(n).g(n)) avec f(n) = max(f_1(n),f_2(n)).

Règle 5 (for)

Pour une boucle for, il suffit de ‘’traduire’’ le for en while.

Donnons de simples exemples de complexité avec des for où ici aussi n est la taille du problème :

for i in range(10):

  traitement

est en O(10.f(n)) où O(f(n)) est la complexité d’une exécution du traitement et donc le code complet est également en O(f(n))

for i in range(n):

  traitement

est en O(n.f(n)) où O(f(n)) est la complexité d’une exécution du traitement.

Ainsi le produit de matrice (M.L par L.N) est en O(M.L.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.

Application des règles de calcul

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):

res = 0                    #1

i = 1                      #2

while i < n     :          #3

   if s[i][0] < s[res][0]: #4

      res = i              #5

   i = i+1                 #6

return res                 #7

Décomposition d’un traitement en suivant la structure

les 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, les instructions 4-5 correspondant à  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 ( 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é

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.

Complexité des opérations sur les ensembles

L’implémentation des ensembles est similaire à celle des dictionnaires.

Complexité des opérations sur les dictionnaires