时间戳

首页 > 解决方案 > 如何用代入法求解 () = 2(/2) +1

recursion - 如何用代入法求解 () = 2(/2) +1

问题描述

在这里，我得到了一个递归函数，我想用替换方法 （数学归纳法）解决这个问题（找到时间复杂度）。

() = 2(/2) +1

在提到的问题中，我们的猜测应该是Ω(log n)。实际上，我使用数学归纳法来证明T(n) = O(n)然后因为n = Ω(log n)所以T(n) 也是如此。但我没有成功地证明它正确。

我已经看到了之前询问过的这个函数的所有答案，但没有用 Substitution Method 解决。你能帮我用这种方式证明吗？

标签： recursiontime-complexitybig-osubstitution

解决方案

你的策略是正确的。我们通过归纳证明T(n) = Theta(n)。

我们假设 wlog 为初始条件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)等等。

推荐阅读