如何用代换法求解T(n) = 2(T/8) +n
如何用代换法求解T(n) = 2(T/8) +n
提问于 2022-09-28 14:37:58
T(n) = 2(T/8) +n
我必须用代换法和数学归纳法来解决这个问题。
使用主方法，由例3得到的答案是T(n) =θ(n)。
因此，使用代换法，应该得到同样的答案。我说的对吗？
推导T(n) = O(n)是简单的
但是当我试图通过假设T(k) >= ck (其中k< n)证明T(n) =Ω(n)时
则T(n) = 2T(n/8) +n >= 1/4*cn +n= cn -(3/4cn-n) >= cn <-错误
通过减去或添加一个低阶项也是不可能解决的。
如何仅用替换法证明T(n) =θ(n)？
回答 1
Stack Overflow用户
发布于 2022-09-28 15:00:06
你可以证明T(n) >= n。T(n) = 2T(n/8) +n >= n，如果你想使它变得更复杂，可以用它代替，那么T(n) = 2T(n/8) +n >= n/4 +n >= n.
我没有仔细研究过您的证明，但似乎您假设可以为所有的c，而不是某些特定的c(在我的证明中，c=1)证明它。也许这个野心过大的假设会给你带来麻烦。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73883394
复制相关文章
相似问题
腾讯云开发者
