Complexité
Evaluer la complexité en nombre de multiplications de ... Etablir une relation de
récurrence permettant d'évaluer la complexité de cet algorithme récursif de
multiplications .... Corrigé. Question 1. Il est facile de montrer les invariants
suivants :.
part of the document
Complexité
Deuxième partie : recursivité
Exercice 20
Résoudre léquation de récurrence un=3un-1-2un-2+n, u0=0, u1=0
Commençons par rechercher les solutions de l'équation homogène correspondante : un=3un-1-2un-2
Pour cela, considérons le polynôme caractéristique associé : x2-3x-2=0.
Il a deux racines simples 1 et 2.
Donc l'ensemble des solutions de l'équation homogène est de la forme h n =a2n+b1 n
On sait qu'il existe une solution particulière de l'équation non homogène de la forme sn= P(n)1 n, où P(n) est un polynôme en n de degré 2. On cherche donc c,d,et e tels que
sn =cn2+dn+e soit solution de l'équation un=3un-1-2un-2+n
On doit donc avoir cn2+dn+e= 3(c(n-1)2+d(n-1)+e)-2(c(n-2)2+d(n-2)+e)+n pour tout n
Et donc c=3c-2c [coefficient du terme en n carré]
d=3(-2c+d)-2(-4c+d)+1 [coefficient du terme en n]
e=3(c-d+e)-2(4c-2d+e) [terme constant]
D'où 2c+1=0 et 5c-d=0 et finalement on obtient comme solution particulière
sn =-(1/2 )n2 -(5/2)n+e
Toutes les solutions de l'équation un=3un-1-2un-2+n , sont donc de la forme
un= a2n-1/2 n2 -5/2n+k
Puisque les deux premiers termes de la suite sont nuls, on a 0=a+k et 0=2a-3+k donc a=3 et k=-3
Et finalement un= 3.2n-(1/2) n2 -(5/2)n-3
Exercice 21
Evaluer la complexité en nombre de multiplications de
public int sommeFactoriel(int n) {
int factorieln ;
if (n
