如何用代换法求解() = 2(/2) +1
如何用代换法求解() = 2(/2) +1
提问于 2020-10-22 14:58:54
这里我得到了一个递归函数，我想用替换方法(数学归纳法)来解决这个问题(求出时间复杂度)。
() = 2(/2) +1在提到的问题中，我们的猜测应该是Ω(log )。实际上，我用数学归纳法证明了T(n) = O(n)，因为n =Ω(log n)，所以T(n)太 .but I没有成功地证明它。
我已经看到了这个函数之前的所有答案，但是它们没有用替代方法来解决。你能帮我用这种方式证明吗。
回答 1
Stack Overflow用户
发布于 2020-10-25 14:59:19
你的策略是正确的。我们通过归纳法证明了T(n) = Theta(n)。
我们假设w.l.o.g.初始条件T(n) = 1。
归纳假说：T(n) = 2n - 1。
基本案例：T(1) = 1 = 2 * 1 - 1。
归纳案例：
T(n) = 2T(n/2) + 1
= 2 (2n/2 - 1) + 1 (inductive hypothesis)
= 2n - 1 (QED)因此，T(n) = Theta(n)，并从那里跟随，例如，T(n) = Omega(log n)等。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64485000
复制相关文章
相似问题
腾讯云开发者
