VI-La Complexité en Python
VI-La Complexité en Python
VI-La Complexité en Python
en python
MP1
2019/2020
1
2 Introduction
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 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
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:
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é
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:
Fin