Correction TD 1 : Complexité
Exercice 1 :
1. Cout≤ max(1,3)+1= 4
2. Cout= 5*2= 10
3. for i in range(0,n):
Ce programme contient deux boucles :
for j in range(i,n):
Boucle i allant de 0 à (n-1) : s'exécute n fois
print("salut") Boucle j qui s'exécute en fonction de i
Pour i=0 la boucle j s'exécute de 0 à n-1 n fois
Pour i=1 la boucle j s'exécute de 1 à n-1 (n-1) fois
…
Pour i=n-1 la boucle j s'exécute de 0 à n-1 1 fois
𝒏(𝒏+𝟏)
Au total nous avons : n+(n-1)+(n-2)+…+2+1 = 𝟐
On peut calculer la complexité par une autre méthode :
Soit C(n) la complexité de ce programme, nous avons :
∑ ∑ =∑ = n+(n-1)+ … + 1 =
4.
Ce programme contient une seule boucle while dont le
i=1
compteur i est multiplié chaque fois par 2. On
while i<= n :
print('Salut') commence par le calcul nombre de répétition de la
i = 2* i boucle pour déduire la complexité :
Au début de la première exécution de la boucle i = 1 = 20
Au début de la deuxième exécution de la boucle i = 2 = 21
Au début de la troisième exécution de la boucle i = 4 = 22
Au début de la Kème exécution de la boucle i = 2k-1
La dernière exécution de la boucle sera quand 2t-1 = n avec t le nombre d’itérations de la boucle, donc
t= log2(n) + 1
C(n)=( log2(n) + 1)*(3+1)+1+1=4*log2(n) + 6
5.
Ici nous avons la boucle for qui s'exécute n fois et la
i=1
boucle while log2(n)+1 fois (c'est la même que celle
while i<= n :
du programme précédent).la complexité dans ce cas
for j in range(0,n) :
print('Salut') est : C(n)= t*(n+2+1)+1+1=n* log2(n)+n+ 3*log2(n)+5
i = 2* i
6. (DL)
1
Exercice 2 :
def grands(L, x):
# initialiser le décompte (nb) avec 0
nb = 0
# Puis on compare x à chaque élément de la liste
for i in L:
# Si un élément est supérieur à x, incrémentez nb par 1
if i > x:
nb += 1
return nb
T(n)= 3*n+2 (avec n la taille de la liste L)
Exercice 3 :
def is_palindrome(a):
for i in range(len(a)//2):
if a[i] != a[-i-1]:
return 0
return 1
Dans cette fonction :
on parcourt la moitié de la chaîne de caractères “a”. Ici, len(a) désigne la longueur de la chaîne, et len(a)//2
représente le quotient de la division euclidienne de cette longueur par 2. Ainsi, si “a” a une longueur impaire, on
s’arrête au caractère juste avant celui du milieu;
dans la boucle for, on teste si le caractère d’indice i est différent du caractère d’indice -i-1. Il faut ici faire
attention au fait que, par exemple, a[0] représente le 1er caractère alors que a[-1] représente le dernier, d’où le
décalage : on ne marque pas a[-i] mais a[-i-1]. Si les caractères sont différents alors la chaîne n’est pas un
palindrome. On retourne donc 0, ce qui stoppe la boucle;
on finit par retourner 1 si 0 n’a pas été retourné.
Opérations élémentaires de la boucle for : deux lecture a[i] et a[-i-1], un teste et return répéter len(a)//2 fois
T(n) ≤ 4*n/2+1=2*n+1 = O(n) avec n=len(a)
Exercice 4 :
def prefixe1(M,S): def prefixe2(M,S):
n=len(M) if S[:len(M)]== M:
for i in range(n): return True
if M[i]!=S[i]: return False
return False
return True
T(n)=1+n*(2+1+1)+1+O(1) =O(n) T(n)=n+2=O(n)
Au pire des cas S et M seront identique donc n
Avec O(1) la complexité de len(L) comparaisons pour S[:len(M)]==M
Exercice 5 : DL
