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?
InformationsquelleAutor evenodd | 2014-09-15