T(n) = 2T(n/2) + O(1) 的时间复杂度是什么？

Question

我希望了解我的递归方法的时间复杂度： T(n) = 2T(n/2) + O(1) 我看到有人说它的时间复杂度是O(n)，但我不知道为什么，我这样解决：

T(n) = 2T(n/2) + 1
T(n-1) = 4T(n-1/4) + 3
 T(n-2) = 8T(n-2/8) + 7
......  …………..  ..
T(n) = 2^n+1 T (n/2^n+1) + (2^n+1 - 1) 

- noor

---

这应该会有所帮助 https://www.quora.com/What-is-the-complexity-of-T-n-2T-n-2-+-C-using-recurrence-equations - Emil Hotkowski

主定理。您的展开式不正确，因为2的指数不是 n。 - meowgoesthedog

@meowgoesthedog 我知道这不正确，我还有点困惑如何找到t(n-n)。 - noor

你应该考虑每一步实际在做什么。T(n) 是以 T(n/2) 为基础的，所以 T(n-1) 并不相关。你还以一种不合理的方式进行替换 - 你有 T(n-1) = 2T((n-1)/2) + O(1)，但是你却用 T(n) 替换了它，而不是用 T((n-1)/2)。你也在计算到 T(1)，而你只需要计算 T(n)（将 T(n/2) 替换为 T(n)，而不是反过来）。 - Bernhard Barker

Answer 1

我认为你对递归关系的理解有误。你可以这样想：

如果T(n)表示函数T()在输入n时的值，则该关系表明输出是当前输入的一半的两倍再加一。因此，对于输入n-1的输出即T(n-1)，将比该输入的一半的两倍多一个，即T(n-1) = 2*T((n-1)/2) + 1。

上述类型的递归关系应按Yves Daoust的答案解决。有关递归关系的更多示例，请参考this。

- Chaman Agrawal

Answer 2

考虑到 n=2^m，这使得你可以写成：

T(2^m)=2T(2^(m-1))+O(1)

或者通过表示 S(m):= T(2^m)，

S(m)=2 S(m-1) + O(1),

2^m S(m)=2 2^(m-1)S(m-1) + 2^(m-1) O(1)

最后,

R(m) = R(m-1) + 2^(m-1) O(1).

现在通过归纳法，

R(m) = R(0) + (2^m-1) O(1),

T(n) = S(m) = 2^(1-m) T(2^m) + (2 - 2^(m-1)) O(1) = 2/n T(n) + (2 - n/2) O(1).

- user1196549

Answer 3

有几个规则可能需要记住。如果您能记住这些简单的规则，那么主定理就非常容易解决递归方程。以下是需要记住的基本规则：

case 1) If n^(log b base a) << f(n) then T(n) = f(n)
case 2) If n^(log b base a) = f(n) then T(n) = f(n) * log n
case 3) 1) If n^(log b base a) >> f(n) then T(n) = n^(log b base a)

现在，让我们使用上述方程式解决这个递归问题。

a = 2, b = 2, f(n) = O(1)
n^(log b base a) = n = O(n)

这是上述方程中的第3种情况。因此，T(n) = n^(log b base a) = O(n)。

- Ishan Yadav