Inscription / Connexion Nouveau Sujet
Solution de Récurrence Demandé
Soit f(n) le nombre de comparaisons nécessaires au pire cas pour exécuter tri par fusion sur un tableau de taille n. Alors f(n) satisfait la récurrence
f(1)=0; f(n)=f([n/2])+f([n/2])+n-1 si n>1
Trouvez la solution exacte de la récurrence h(1)=0; h(n)=2h(n/2)+n-1 si n>1 quand n est une puissance de 2
Trouvez une fonction g(n) sans addition, soustraction ou multiplication par une constante telle que h(n) 
O(g(n)) et g(n) O(h(n))
Démontrez que f(n) O(g(n)) et g(n) O(f(n))
Cette question comporte 3 partie. J'ai deja formulé une réponse partielle, mais j'accroche a quelques endroits, pouvez-vous m'aidez à la résoudre.
Merci.
A ce que je vois, je ne suis pas le seul a le trouver difficile ce numero!
Pour la partie 1 : Fais un changement de variable, trouve ton polynome caractéristique et fais l'équation p(x), dans ton cas cela va donner si n = 2k
hk = 2hk-1 + k - 1 pour k>1 et 1 pour k = 0
ensuite résoud ce systeme comme un systeme non homogène
donc, p(x) = (x-2)(x-1)(x-1)
donc hk = a2k + b + ck
on ramene en fonction de n avec k = lgn
hn = an + b + c*lgn
et on trouve les valeurs de a,b,c par remise dans la récurrence ou par valeur calculer à la main avec la récurrence
hn est dans 
(n) ce qui est tres facile a demontrer
pour le dernier point il suffit de demontrer que f(n) est aussi dans n en résolvant la récurrence
Voila, j'Espere que cela répond à tes questions et que tu comprends mieux
Annuler
connectez vous
analyse en Bts