VI-La Complexité en Python

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 22

Analyse de la complexité

en python
MP1
2019/2020

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 If cond : C1 : temps d’execution de la C1+max(C2,C3)
conditionnelles bloc1 condition
else: C2:temps d’execution du bloc1
bloc2 C3:temps d’execution du 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
Bloc1 condition. M*max(C1,C2)
C2: temps d’exécution du bloc1
M: le nombre de boucles espérés
Calcul du coût du problème recherche du maximum
5
d’une liste

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
1 reste + 1 comparaison
if n%i==0: ……………… …………………………………
.
1 return
return(False) …………
1 return
return(True) ………………
7 Calcul du coût de la puissance

def puissance(x,n):
La coût de la fonction est:
1
m=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.
1/ On remplace les constantes
2) on combine ces coûts conformément aux multiplicatives par 1:
règles vues précédemment. 1n3-1n2+4
2/On annule les constantes additives
3) on simplifie le résultat grâce aux règles de Exemple
1n3-1n2=n3-n2
simplifications suivantes:
3/ On conserve le terme dominant:
 On remplace les constantes g(n)= n3
multiplicatives par 1.
 On annule les constantes additives . La complexité : O(g(n))=O(n3)
 On conserve le terme dominant.
10
Les fonctions O des structures algorithmiques
usuelles
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 O(max(f1(n), f2(n),….fk(n))
simples: respectives de Inst1,Inst2…instk sont
Inst1 O(f1(n)), O(f2(n))…. O(fk(n))
Inst2
.
.
instk
Structures conditionnelles On suppose que les complexités O(max(g(n), f1(n), f2(n))
If cond : respectives de la condition , Bloc1
bloc1 et bloc2 sont O(g(n)), O(f1(n))et
else: O(f2(n))
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


while i<=100: boucle 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
j=1
boucle for 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
while(i<=n): O(n) est:
O(1)+O(1)*O(n)+O(1) =O(n)
fact=fact*I 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(log10(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
20 Calcul de la complexité
Exercice1
Dites si les affirmations suivantes sont vrais ou fausses:

 2*n+3=O(n)………………………………………………

 2n+log(n)=O(n2) ………………………………………………

 2n7+5n4+3n2+1=O(n7) ………………………………………………

 5n3+3*n*log(n)+6n=O(n3) ………………………………………………

 3log(n)+2=O(log(n)) ………………………………………………

 2n+100log(n)=O(log(n)) ………………………………………………

 2n+2=O(2n) ………………………………………………
21 Calcul de la complexité
Exercice2
Quelle est la complexité de la fonction suivante:

def calcul(n): Réponse…………………


p=0 …………………………….
……………………………
for i in range(1,n*n+1): ……………………………
j=i ……………………………
……………………………
while(j!=0): …………
p=p+1
j=j//2
return(p)
22 Calcul de la complexité
Exercice3
Tri par insertion
Calcul de la complexité:
Procédure tri_Insertion (var tab : tableau entier [N])
i, k :entier ; ………………………………………………………………………
tmp : entier ;
………………………………………………………………………
Début
Pour i de 2 à N faire ………………………………………………………………………
tmp  tab[i];
………………………………………………………………………
k  i;
Tant que k > 1 ET tab[k - 1] > tmp faire ………………………………………………………………………
tab[k]  tab[k - 1];
kk - 1; ………………………………………………………………………

Fin Tant que


………………………………………………………………………
tab[k]  tmp;
Fin pour …………………………………………………………

Fin

Vous aimerez peut-être aussi