Complex It e

CPGE-REDA SALAOUI –AGADIR MP-PSI-TSI
TD : Complexité
- Correction -
Exercice 1
On considère le programme suivant:
Def Algo(n):
for i in range(0,n):
Algo1(n)
Algo2(n)
Algo3(n)
 Sachant que Algo1(n) s'effectue en temps O(log(n)),Algo2(n) en temps O(n)etAlgo3(n) en temps O(n2),
Quelle est la complexité de Algo(n)?
La boucle for exécute n fois une procédure qui coute O(log n), donc la boucle for coutera O(n.log n).
L’algorithme au total coutera donc : O(n.log n) + O(n) + O(n2).
Donc la complexité de Algo(n) est : O(n2).
Exercice 2 :
Quelle est la complexité du programme suivant :
def Algo(n):
res = 1;
res = res + i
for j in range(0,i):
res = res * (i+j)
return res
Calculons le nombre d’opérations : T(n).
T(n)= 2 + 2.n + ∑𝒏−𝟏 𝒊−𝟏
𝒊=𝟎 ∑𝒋=𝟎 𝟑
T(n)= 2 + 2.n + ∑𝒏−𝟏

𝒊=𝟎 𝟑𝒊
T(n)= 2 + 2.n + ∑𝒏−𝟏
𝒊=𝟎 𝟑𝒊
𝒏(𝒏−𝟏)
T(n)= 𝟐 + 𝟐. 𝐧 + 𝟑. 𝟐
Complexité : O(n2)
Exercice 3 :
Quelle est la complexité du programme suivant:
def f(x, n): C(0)= 1
if n < 1: O(1) C(n)= 1 + n + C(n/2)
return n
S = 0 Complexité : O(n)
for i in range(0,n): O(n)
S += x/(i+n)
return S + f(x,n//2) O(log2(n))
1
Exercice 4
1- Que vaut la complexité de l'algorithme suivant:
i=1
while i <= n :
i=i*2
soit k le nombre d’itérations de la boucle while :

dans la dernière itération on aura :
((1*2)*2)*2)…*2 ) > n
2k<= n
k <=log2(n))
Complexité : O(log2(n))
2- Le code ci-dessous consiste à programmer la fonction remove. Analysersacomplexité?

def SupprimerElement(L,a):
i=0
if a in L: O(n)
while L[i]!=a: O(n)
i=i+1:
L[i:i+1]=[] O(1)
Complexité : O(n)
Exercice 5
Soient les 3 fonctions suivantes permettant de calculer la valeur d'un polynôme.
p(x) = a0+a1x+a2x2+...+anxn
en un point x (c'est-à-dire pour une valeur x donnée).
Les coefficients du polynômes sont stockés dans une liste : A=[ a0, a1, a2..., an-1 , an]
def f1(A,x) :#méthode naïve
n =len(A)
p=A[0]
for i in range(1,n) :
p = p + A[i]* x**i
return p
x**i : n’est pas une opération élémentaire : son cout pour i allant de 1 à n = n(n+1)/2
T(n)=4+3n+(1+2+3…+n-1)
T(n)=4+3n+((n-1).n)/2
T(n)= (n2 +5n)/2 +4
Complexité : O(n2)
2
def f2(A,x) :# elle utilise le fait que xi = xi-1* x
n =len(A)
p=A[0]
q = 1
for i in range(1,n) :
q = q * x
p = p + A[i] * q
return p
T(n)= 4 +5(n-1)
T(n)= 5n-1
Complexité : O(n)
#algorithme de Horner ;
il calcule, DANS CET ORDRE, les valeurs de :an, anx+an-1, puis (anx+an-1) x + an-2, etc.
def f3(A,x) :# utilisant la méthode de Horner
n =len(A)
p = A[n-1] ;
for i in range(n-1,0,-1) :
p = p*x + A[i-1]
return p
T(n)= 4 +4(n-1)
T(n)= 4n+1
Complexité : O(n)
Exercice 6
1- Écrire une fonction qui prend un tableau d’entiers T en argument et renvoie le tableau des sommes
cumulées croissantes correspondantes, autrement dit un tableau S de même taille dont la k-ième
composante vaut :
𝑘
𝑆[𝑘] = ∑ 𝑡[𝑖]
𝑖=0
2- Evaluer la complexité de cette fonction.

3- Est-il possible d’en écrire une version plus efficace ? Donner alors sa complexité
Correction :
1. 2.
def somme(L): La complexité :

n= len(L)
s=[0]*n On compte le nombre d’opérations :
for i in range(n):
for j in range(i+1): 𝑛(𝑛 + 1)
5 + 2.
s[i]=s[i]+L[j] 2
return s Complexité de cette fonction est en O(n2)
3.Une version plus efficace :
def somme2(L): On compte le nombre d’opérations :

n= len(L)
s=[0] * n 6 + 2(𝑛 − 1) = 2. 𝑛 + 4
s[0]=L[0]
for k in range(1, n): La complexité de cette fonction est en O(n)
s[k]= s[k-1] + L[k]
return s
3
Exercice 7
Soit u la suite définie par u0 = 1 et pour n ∈ N, un+1 = sin(un).
1. Écrire une fonction nommée suite prenant n ∈ N en argument et renvoyant un.
2. Que calcule la fonction suivante : def mystere(n):
s = 0
for k in range(n+1):
s = s + suite(k)
return s
3. Déterminer en fonction de n le nombre d’additions et de calculs de sinus nécessaires pour calculer

mystere(n).
4. Écrire une autre fonction qui renvoie les mêmes valeurs que mystere mais avec une meilleure
complexité.
Correction :
1. Écrire une fonction nommée suite prenant n ∈ N en argument et renvoyant un.
from math import sin

def suite(n):
u = 1
for i in range(n):
u = sin(u)
return u
2. Que calcule la fonction suivante :
def mystere(n): La fonction mystere calcule la somme des termes de

s = 0
u0(c-a-d suite(0) ) à un (c-a-d suite(n)) : ∑𝑛𝑘=0 𝑢𝑘
for k in range(n+1):
s = s + suite(k)
return s
3. le nombre d’additions et de calculs de sinus nécessaires pour calculer mystere(n) :

A chaque passage dans la boucle de mystere , on a une addition et un appel de la fonction suite.
A chaque passage dans la boucle de suite, on a un calcul de sinus.
𝑛 𝑘−1 𝑛
𝑛(𝑛 + 1) 𝑛2 3𝑛
∑ (1 + ∑ 1) = (𝑛 + 1) + ∑ 𝑘 = (𝑛 + 1) + = + +1
2 2 2
𝑘=0 𝑖=0 𝑘=0
Donc la fonction mystère est de complexité = O(n2)
4. Écrire une autre fonction qui renvoie les mêmes valeurs que mystere mais avec une meilleure complexité.
Cette fonction a une complexité linéaire (c’est à dire en

def mystere(n): O(n)) car elle est composée d’une boucle contenant 4
u = 1 opérations élémentaires (2 affectations, une addition et
s= 0 le sinus). (on a supposé que le cout de sin(u)=1)
for k in range(n):
u = sin(u) Si on avait appelé la fonction suite dans la boucle pour
s = s + u calculer uk, on aurait eu une complexité quadratique (en
O (n2)).
return s 4
Un appel avec n = 106 est raisonnable avec la version
linéaire, mais pas avec la version quadratique.

Complex It e

Transféré par

Droits d'auteur :

Formats disponibles

Complex It e

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Complex It e

Transféré par

Droits d'auteur :

Formats disponibles

CPGE-REDA SALAOUI –AGADIR MP-PSI-TSI

T(n)= 2 + 2.n + ∑𝒏−𝟏

return S + f(x,n//2) O(log2(n))

soit k le nombre d’itérations de la boucle while :

2- Le code ci-dessous consiste à programmer la fonction remove. Analysersacomplexité?

2- Evaluer la complexité de cette fonction.

def somme(L): La complexité :

return s Complexité de cette fonction est en O(n2)

3.Une version plus efficace :

def somme2(L): On compte le nombre d’opérations :

3. Déterminer en fonction de n le nombre d’additions et de calculs de sinus nécessaires pour calculer

from math import sin

2. Que calcule la fonction suivante :

def mystere(n): La fonction mystere calcule la somme des termes de

3. le nombre d’additions et de calculs de sinus nécessaires pour calculer mystere(n) :

Donc la fonction mystère est de complexité = O(n2)

Cette fonction a une complexité linéaire (c’est à dire en

Vous aimerez peut-être aussi