Résolution de la relation de récurrence $ T (n) = 2T (\ lfloor n / 2 \ rfloor) + n $

Question

Résoudre la relation de récurrence $ T (n) = 2T (\ lfloor n / 2 \ rfloor) + n $.
Le livre à partir de laquelle cet exemple est faussement revendications que $ T (n) = O (n) $ par deviner \ leq cn T (n) $ $ et soutenant

$ \ qquad \ begin {align *} T (n) et \ leq 2 (c \ lfloor n / 2 \ rfloor) + n \\ & \ leq cn + n \\ & = O (n) \ quad \ quad \ quad \ longleftarrow \ texte {mal !!} \ end {align *} $

depuis $ c $ est une erreur constante.Le est que nous n'avons pas prouvé exact sous forme de l'hypothèse inductive.

Au-dessus, j'ai cité textuellement ce que dit le livre. Maintenant, ma question est pourquoi ne pouvons-nous écrire $ cn + n = dn $ où $ d = c + 1 $ et maintenant nous avons T (n) \ leq dn $ et, par conséquent T $ (n) = O (n) $ $?

Note:

1. La bonne réponse est $ T (n) = O (n \ log n). $
2. Le livre que je fais référence ici est Introduction aux algorithmes par Cormen et al., À la page 86, 3ème édition.

Answer 1

Les auteurs donnent la réponse:

  

L'erreur est que nous n'avons pas prouvé la forme exacte de l'hypothèse d'induction, qui est, que $ T (n) \ leq cn $.

Certes, qui est difficile à comprendre si vous n'êtes pas habitué à faire inductions (à droite), parce qu'ils ne le font pas explicitement l'induction / rigoureusement. En bref:. Vous devez avoir un $ c $ constant pour tous $ n $, mais cette preuve (dé) construit un grand nombre (un par $ n $)

---

Dans de temps, rappelez-vous ce que T $ (n) \ O (n) $ signifie:

$ \ qquad \ displaystyle \ existe c \ in \ mathbb {N}. \, \ Existe n_0 \ in \ mathbb {N}. \, \ Forall n \ geq n_0. \, T (n) \ leq cn $

ou, ce qui revient,

$ \ qquad \ displaystyle \ existe c \ in \ mathbb {N}. \, \ Forall n \ in \ mathbb {N} T (n) \ leq cn $.

La deuxième forme fonctionne mieux pour une induction comme vous le savez l'ancre. Vous avez donc besoin un $ constant c $ qui fournit une limite supérieure pour tous n $ $.

nous allons inspectent ce que l'induction fait:

• ancre à induction. L'ancre de $ T $ est pas explicitement donnée, mais il est constant, donc nous trouvons un $ adapté $ c
• hypothèse d'induction. Il y a quelque $ c $ pour que $ T (k) \ leq cn $ pour tout k $ \ leq n $, pour quelque arbitraire mais fixe $ n $
• étape inductive. Comme représenté sur la question, construire $ d> c $ $ T de telle sorte que (n + 1) \ leq $ dn

Alors, en effet, nous construisons une nouveau constant pour chaque n $ $. Cela ne correspond pas à la définition de $ O $ du tout! Et, pire encore, il ne veut rien dire. tous fonction peut être "limitée" par toute autre fonction si vous pouvez régler le facteur avec $ n $

En ce qui concerne la preuve de l'induction, $ c $ doit faire partie de la demande (et il est caché dans le $ O $), qui est lié « à l'extérieur » de l'induction. Ensuite, le même $ c $ apparaît dans l'ancre, l'hypothèse et l'étape. Voir la dernière partie de cette réponse pour un exemple.