La résolution de récurrence T(n) = 2T(n/2) + Θ(1) par substitution
Donc je suis assez sûr que c'est de O(n) (mais c'est peut-être pas?), mais comment voulez-vous résoudre ce problème avec la substitution?
Si vous supposez T(n) <= c * n, qu'est-ce que l'induction étapes?
- Dites-nous pourquoi vous pensez que c'est O(n)
- En fait, peut-être qu'il faut être plus grand? Parce que si vous remplacez O(n), vous vous retrouvez avec T(n) <= cn + d. Et d doit être positive car elle ne peut pas l'être. C'est peut-être n^2
- Cette question semble être hors-sujet, car il n'est pas sur la programmation. Voir Quels sont les sujets que pouvez-vous nous parler ici dans le Centre d'Aide. Peut-être Informatique Stack Exchange serait un meilleur endroit pour demander cela.
- Essayez de s'attaquer à deux est un peu plus facile des problèmes: T(n) = 2 * T(n/2), et T(n) = T(n/2) + O(1). Lequel de ces problèmes est la plus semblable à la vôtre? Pouvez-vous appliquer les résultats à votre problème?
Vous devez vous connecter pour publier un commentaire.
Tout d'abord,je tiens à assumer clairement que Θ(1)=k,une constante.
Prochain,instance en utilisant la méthode de substitution, on obtient
Si vous assumez comme
T(n) <= c * n
,vous devriez commencer avec T(1) et supposons que T(n) pour être correct,et ensuite de montrer qu'il est correct pour T(n+1) en utilisant l'hypothèse de T(n).BTW,votre hypothèse était la bonne!
2^m T(n/2^m) + (2^m - 1)k
. Maintenant, pour faireT(1)
, nous laissons2^m = n
qui nous donne la ligne 6.Pour des raisons de simplicité, supposons que le O(1) terme se cache une constante c, de sorte que la récidive est vraiment
Supposons pour simplifier que T(1) = c.
Vous aventurer un (bon) suppose que
Pour certaines constantes a et b. Nous allons essayer de le prouver par induction.
Pour n = 1, nous avons besoin de a et b telles que
Pour l'étape inductive, nous voulons
En substituant notre deviner donne
Avis que si 2b + c = b, la gauche de cette expression serait un + b, la limite supérieure dont nous avons besoin. Donc, nous avons besoin de choisir a et b tels que
Un choix possible qui travaille ici est a = 2c et b = c, ce qui donne T(n) <= 2cn - c = O(n).
Espérons que cette aide!