Correction TD : Complexité
Exercice 1 :
a) Fonction prodMat :
Ici nous avons trois boucles imbriquées allant toutes de 0 à n-1. La complexité est
proportionnelle au nombre d'instructions de la boucle d'indice k.
Au total : ∑ ∑ ∑
D’où : O(n3)
b) Fonction recherche :
• Meilleur des cas : la valeur x se trouve au débit de la liste la boucle ne s’exécutera
qu’une seule fois, donc la complexité est (1)
• Pire des cas : La valeur x ne se trouve pas dans la liste, la boucle for s’exécutera n
fois avant que la fonction retourne la valeur Faux, la complexité est ( )
Exercice 2 :
1 def grands(L,x) :
2 compt = 0
3 n = len(L)
4 for i in range(n) :
5 if L[i] > x :
6 compt += 1
return compt
7
Complexité :
les lignes 2et 3 contiennent deux affectations, on conclut donc que avant la boucle la
complexité est O(1).
Pour chercher les valeur supérieurs à x, on doit parcourir tout les éléments de la liste
ce qui fait que les opérations à l’intérieurs (qui ont une complexité O(1)) vont se
répéter n fois. Donc la complexité de la boucle for est O(n)
Page 1 sur 5
On déduit donc que la complexité de la fonction est O(n)
Exercice 3 :
1 def prefixe(M,S) :
2 if len(M) >len(S) :
3 return False
4 n = len(M)
5 for i in range(n) :
6 if M[i] != S[i] :
7 return False
8 return True
Complexité :
le nombre de comparaisons :
- le test len(M) > len(S)
- les comparaisons à l'intérieur de la boucle for : n
le total est : n + 1 comparaisons
On déduit que la complexité est O(n)
Exercice 4 :
def fact(n):
f=1
for i in range(1,n+1) :
f*=i
return f
def seuil(M):
i=1
while(fact(i)<=M):
i+=1
return i
def est_divisible(n):
f=fact(n)
if f%(n+1)==0:
return True
return False
def mystere(n) :
Page 2 sur 5
s=0
for k in range(1,n+1):
s = s + fact(k)
return s
Calcul du nombre de multiplications :
La fonction mystere ne contient aucune multiplication mais contient un appel à la
fonction factoriel (fact) qui –par contre – contient une à l’intérieur de la boucle for
L’appel fact(1) : génèrera 1 multiplication
L’appel fact(2) : génèrera 2 multiplications
L’appel fact(3) : génèrera 3 multiplications
…
L’appel fact(n) : génèrera n multiplications
Au total : 1+2+3+…+n =
Nous avons donc une complexité : O(n²)
def mystere2(n) :
s=0
f=1
for k in range(1,n+1):
f =f*k
s=s+f
return s
*
Exercice 5 : def dicho_rec(ls,debut,fin,val) :
if debut > fin :
a) Dichotomie récursive : return -1
else :
Le pire des cas pour la fonction m=(debut+fin)//2
dichotomie, c'est quand on cherche if ls[m]==val :
une valeur qui n'existe pas dans la return m
liste. Dans ce cas nous avons : elif ls[m]>val :
return dicho_rec(ls,debut,m-1,val)
T(n) = T(n/2) + α else :
return dicho_rec(ls,m+1,fin,val)
Page 3 sur 5
Avec :
• T(n/2) : C'est le cout de l'une des deux appels récursifs, Ce cout est normalement
le même puisque les fonctions reçoivent en paramètre la moitié de la liste et donc
le même nombre d'éléments.
• α : Le cout de l'exécution de la fonction dicho_rec une seule fois (une valeur
constante ici)
T(n)=T(n/2)+α
T(n)= T(n/4)+2α = T(n/2²)+ 2α
T(n)= T(n/23)+3α
Au kème étape :
T(n)= T(n/2k)+kα
n/2k =1 k=
T(n)= T(1) + α
D'où : O ( )
b) Dichotomie itérative :
La complexité de cette fonction est proportionnelle au nombre d'exécution de la
boucle while
def dicho_iter(ls,val) :
Soit n la dimension de la liste ls
debut=0
1ére exécution de la boucle while la nouvelle fin=len(ls)-1
dimension de la liste est : n/2 while debut<=fin :
moitie=(debut+fin)//2
2ème exécution de la boucle while la nouvelle
if ls[moitie]==val :
dimension de la liste est : n/4= n/2² return moitie
… elif val>ls[moitie] :
debut=moitie+1
kème exécution de la boucle while la nouvelle else :
dimension de la liste est : n/2k fin=moitie-1
return False
la dernière exécution de la boucle while correspond à debut=fin n/2k =1
Donc : k=
D'où : O ( )
Page 4 sur 5
Exercice 6 :
#Version itérative
def entier(B) :
S=0
n=len(B)
for i in range(n-1,-1,-1):
S = 2*S+int(B[i])
return S
# Version récursive:
'''
La fonction possède 2 paramètres :
• B : la chaine contenant la représentation binaire du nombre
• i : un entier représentant les indices de la chaine B, ce paramètre sera
initialisé au moment de l'appel par 0 pour commencer le traitement depuis le
début de la chaine.
def entierRec(B,i) :
n=len(B)
if i==n :
return 0
else :
return int(B[i])+2*entierRec(B,i+1)
Page 5 sur 5
