In [1]: def fact(n):
if n==0 or n==1 :
return 1
return n*fact(n-1)
Soit Cn la complexité de la fonction fact(n)
Si n=0 ou 1, C0 = C1 = O(1)
Sinon, Cn = O(1) + O(1) + Cn−1 = O(1) + Cn−1
alors Cn = O(n)
Soit la suite (Un ) n∈N définie par :
U0 = 5, U1 = −2
Un = Un−1 + 2 ∗ Un−2
In [2]: def U(n):
if n==0:
return 5
elif n==1:
return -2
else:
return U(n-1)+2*U(n-2)
Soit Cn la complexité de la fonction U(n)
Si n=0 ou 1, C0 = C1 = O(1)
Sinon, Cn = O(1) + O(1) + O(1) + Cn−1 + Cn−2 = O(1) + Cn−1 + Cn−2
alors Cn+1 = O(1) + Cn + Cn−1
donc Cn+1 − Cn = Cn + Cn−1 − Cn−1 − Cn−2
alors Cn+1 − 2Cn + Cn−2 = 0
1+√5 1−√5
(E.C) x 3 − 2x
2
+ 1 = 0 → (x − 1)(x
2
− x − 1) = 0 ⇒ (x − 1)(x − )(x − ) = 0
2 2
1+√5 1−√5
alors Cn = α1
n
+ β( )
n
+ γ( )
n
2 2
1+√5
donc Cn = O(( )
n
)
2
Soit la suite (Un ) n∈N définie par :
U0 = 5, U1 = −2
Un = Un−1 + 2 ∗ Un−2
In [ ]: def U(n):
if n==0 :
return 5
elif n==1:
return -2
else:
X,Y=-2,5
for i in range(2,n+1):
X,Y=X+2*Y,X
return X
Soit Cn la complexité de la fonction U(n)
Si n=0 ou 1, C0 = C1 = O(1)
Sinon, Cn = O(1) + O(1) + O(1) + Σ
n
i=2
O(1) + O(1) = O(n)
Ecrire une fonction qui calcule la puissance d'un nombre par la formule suivante :
0
x = 1
1
x = x
x
n
= (x 2 )
2
si n est pair
n−1
x
n
= (x 2 ) x
2
si n est impair
In [5]: def pui(x,n):
if n==0:
return 1
elif n==1:
return x
elif n%2==0:
y=pui(x,n//2)
return y*y
else:
y=pui(x,(n-1)//2)
return y*y*x
Soit Cn la complexité de la fonction pui(x,n)
Si n=0 ou 1, C0 = C1 = O(1)
Sinon,
si nest pair Cn = O(1) + O(1) + O(1) + O(1) + C n + O(1) = C n + O(1)
2 2
si n nest impair Cn = O(1) + O(1) + O(1) + O(1) + C n−1 + O(1) = C n−1 + O(1)
2 2
donc ∃α > 0 tel que Cn ≤ C n + α
2
alors Cn ≤ C n + 2α
22
Cn ≤ C n + 3α
23
....
Cn ≤ C n + kα
2k
pour k = log(n) On a Cn ≤ O(1) + αlog(n) donc Cn = O(log(n))