Analyse de la complexité en

python

1
2 Introduction

 Dans les chapitres précédents on s’est concentré sur l’écriture des scripts et des
fonctions python pour atteindre le bon résultat sans jamais se soucier de l’aspect
performance.
 La performance d’un script est d’une part l’espace mémoire utilisé et d’autre part
le temps mis par le processeur lors du calcul du résultat.
 On parle donc de complexité spatiale et de complexité temporelle.
 Dans ce chapitre, on se focalisera sur l’aspect complexité temporelle.
 Il ne s’agit pas de mesurer le temps d’exécution uniquement ( module time de
python) mais de décrire le comportement asymptotique d’un script lorsque la
taille des données augmente.
 On utilisera donc des fonctions pour décrire l’ordre de grandeur du temps
d’execution.
3
Calcul du coûts des fonctions python(1)
Instructions Désignation Notations Formule du calcul
du coût
Instructions simples Input, print, =, >,<, Une unité de temps d’éxecution 1
!= , ==, +,-,*,/,//,
%,**, break, return

Structures conditionnelles If cond : C1 : temps d’execution de la condition C1+max(C2,C3)

bloc1 C2:temps d’execution du bloc1
else: C3:temps d’execution du bloc2
bloc2
Boucle for for i in range(N): Ci: temps d’exécution du bloc1. N*Ci
Bloc1
4 Calcul du coûts des fonctions python(2)
Instructions Désignation Notations Formule du calcul
du coût
Boucle while while condition: C1: temps d’exécution de la condition.
Bloc1 C2: temps d’exécution du bloc1 M*max(C1,C2)
M: le nombre de boucles espérés
 Calcul du coût du problème recherche du maximum d’une liste
5

def maximum(tab,n):
1
max=tab[0]……………………..
La coût de la fonction est:
for i in range (n):……………….
n
……………………………….
1
if tab[i]>max:…………… 2*n 2+2*n
…………………………………
max=tab[i]…………. .
1
1
return(max)…………………
6 Calcul du coût du test de primalité

def premier (n):

La coût de la fonction est:
n-2
for i in range (2,n): ……… ……………………………….
3*(n-2) 3*(n-2)+1
if n%i==0:1 reste
………………+ 1 comparaison …………………………………
.
return(False) 1…………
return
1 return
return(True) ………………
7 Calcul du coût de la puissance

def puissance(x,n):
La coût de la fonction est:
m=1…………. 1
……………………………….
n
for i in range (1,n+1):…………… 2*n 2*n+2
…………………………………
.
m=m*x………..
1+1
1
return(m)…………………………..
8 Mesure de la complexité
 Le calcul du coût d’une fonction renseigne sur le temps nécessaire à son exécution, mais il
suffit de changer de machine pour que le coût change même avec des données identiques.
 Il est donc plus réaliste de construire une fonction qui décrit le comportement du script
lorsque:
 La taille des données augmente: on parle de comportement asymptotique des
algorithmes ou scripts.
 Et le traitement nécessitant le maximum de temps: on parle de comportement
dans le pire des cas

 Il s’agit de la fonctions d’ordre de grandeur notées O qui permet de borner la fonction de

coût.
 Cette fonction s’appelle « complexité d’un script ou algorithme ».
 9 Mesure de la complexité
Pour calculer la complexité d'un programme :
Soit le coût suivant g(n)=5n3-6n2+4
1) on calcule le coût de chaque partie du programme.
2) on combine ces coûts conformément aux règles vues 1/ On remplace les constantes
précédemment. multiplicatives par 1:
1n3-1n2+4
3) on simplifie le résultat grâce aux règles de
2/On annule les constantes additives
simplifications suivantes: Exemple
1n3-1n2=n3-n2
 On remplace les constantes multiplicatives par 1. 3/ On conserve le terme dominant:
 On annule les constantes additives . g(n)= n3

 On conserve le terme dominant.

La complexité : O(g(n))=O(n3)
 Les fonctions O des structures algorithmiques usuelles
10

Instructions Notations Formule du calcul du coût

Instructions simples Input, print, =, >,<, != , ==, +,-,*,/,//,%,**, O(1)
break, return
Un bloc d’instructions On suppose que les complexités respectives O(max(f1(n), f2(n),….fk(n))
simples: de Inst1,Inst2…instk sont O(f1(n)),
Inst1 O(f2(n))…. O(fk(n))
Inst2
.
.
instk
Structures conditionnelles On suppose que les complexités respectives O(max(g(n), f1(n), f2(n))
If cond : de la condition , Bloc1 et bloc2 sont
bloc1 O(g(n)), O(f1(n))et O(f2(n))
else:
bloc2
11 Calcul du coûts des fonctions python(2)
Instructions Notations Formule du calcul du coût
Boucle for La complexité de Bloc1 est: O(f(n)) O(N*f(n))
for i in range(N):
Bloc1

Boucle while O(g(n)): complexité de la condition. O(M*max(O(f(n),O(g(n)))

while condition: O(f(n)): complexité du bloc1
Bloc1 M: le nombre de boucles espérés
12 Les classes de la complexité(1)
Par ordre de complexité croissant on a les classes suivantes:
 O(1) : complexité constante, pas d'augmentation du temps d'exécution quand le paramètre
croit exp: affectation, comparaison, …
 O(log(n)) : complexité logarithmique, augmentation très faible du temps d'exécution
quand le paramètre croit. Exp: conversion de la base décimale à la base binaire
 O(n) : complexité linéaire, augmentation linéaire du temps d'exécution quand le
paramètre croit (si le paramètre double, le temps double). Exp :somme des n premiers
entiers naturels
 O(n*log(n)) : complexité quasi-linéaire, augmentation un peu supérieure à O(n). Exp:
calcul la somme des chiffres des n premiers entiers naturels
13 Les classes de la complexité(2)
Par ordre de complexité croissant on a les classes suivantes:
 O(n2) : complexité quadratique, quand le paramètre double, le temps d'exécution est
multiplie par 4. exemple :Tri sélection,….

 O(ni) : complexité polynomiale, quand le paramètre double, le temps d'exécution est

multiplie par 2i.

 O(an) : complexité exponentielle, quand le paramètre double, le temps d'exécution est

élevé à la puissance 2.

 O(n!) : complexité factorielle, asymptotiquement équivalente à nn

14 Complexités des boucles multiplicatives (1)

 Certaines boucles partent d’une variable ayant une petite valeur et la multiplient par une constante
jusqu’à ce qu’elle deviennent grande.
 D’autres boucles partent d’une variable ayant une grande valeur et la divise jusqu’à arriver à une
petite valeur.
 La complexité de ce genre de boucle s’écrit comme suit:

O(log base du multiplicateur ou diviseur (n))

15 Complexités des boucles multiplicatives (2)

i=1 # une petite valeur initiale La complexité de la boucle

while i<=100: while est:
i=i*2 # on multiplie i par 2 ……………………………….
# la valeur du multiplicateur est 2 O(Log2(100))
…………………………………
.
16 Complexités des boucles multiplicatives (3)

for i in range(n):
La complexité de la boucle for
j=1
est:
n boucles
while j<=i%2: ……………………………….
O(Log2(n)) O(n *Log2(n))
…………………………………
j=j*2
.
17
Complexités de la fonction factorielle

def factorielle(n):
fact=1 O(1)
O(1)
i=2 O(1)
La complexité de la fonction est:
while(i<=n): O(n)
O(1)+O(1)*O(n)+O(1) =O(n)
fact=fact*I O(1) O(1)*O(n)
O(1)
i=i+1 O(1)
return(fact) O(1)
18 Exemples de calcul de complexité(1)
Exemples d’instructions Complexité
for i in range(n): O(n)
for i in range(1,n+1,2): O(n)
for i in range(1,n//2): O(n)
i=0 O(log2(n))
While (i<n):
……
i=i*2
While (n!=0): O(log2(n))
……
n=n//2
While (n!=0): O(log2(n))
……
n=n//10
19 Exemples de calcul de complexité(2)
Exemples d’instructions Complexité

for i in range(n): O(n2)

for j in range(n):

for i in range(n): O(n2)

for j in range(1,i+1):

for i in range(1,n+1): O(n log2(n))

j=i
while(j!=0):
....
j=j//2