通过代入法解决递归式T(n) = 2T(n/2) + Θ(1)，该问题与编程有关。

Question

我相信这个问题的时间复杂度是O(n)（但也可能不是），但是如何使用替换法来解决它呢？

如果你假设T(n) <= c * n，那么归纳步骤是什么？

- evenodd

---

告诉我们你为什么认为它是O(n)。 - Matthew Herbst

其实，也许它必须更大？因为如果你用O(n)代替，最终得到T(n) <= cn + d。而且d必须是正的，否则不行。也许它是n^2。 - evenodd

尝试解决两个稍微简单一些的问题：T(n) = 2 * T(n/2) 和 T(n) = T(n/2) + O(1)。这两个问题中哪一个最像你的问题？你能将结果应用到你的问题上吗？ - dlev

Answer 1

首先，我想明确假设Θ(1)=k，其中k是某个常数。

接下来，使用替换法进行推导，我们得到

 T(n)=2T(n/2)+Θ(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

如果你将它假设为 T(n) <= c * n，你应该从T(1)开始，并且假设T(n)是正确的，然后通过使用T(n)的假设来证明它对于T(n+1)也是正确的。

顺便说一下，你的假设是正确的！

- Am_I_Helpful

---

在第五行之后，泛化应该是 2^m T(n/2^m) + (2^m - 1)k。现在为了计算 T(1)，我们让 2^m = n，这给出了第六行。 - Muntashir Akon

Answer 2

为简单起见，假设O(1)项隐藏了一些常数c，因此递归实际上是：

T(n) = 2T(n/2) + c

为简单起见，我们也假设T(1)=c。

您正在猜测（正确的）：

T(n) ≤ an + b

对于某些常数a和b。让我们尝试归纳证明这一点。

当n=1时，我们需要a和b满足：

c ≤ a + b

对于归纳步骤，我们希望：

T(n) ≤ 2T(n/2) + c

将我们的猜测代入得到：

T(n) ≤ 2(an / 2 + b) + c = an + 2b + c

请注意，如果2b + c = b，则该表达式的左侧将是an + b，这是我们需要的上限。因此，我们需要选择a和b，使得

c <= a + b

2b + c = c

这里有一个可能可行的选择，即a=2c，b=-c，从而得到T(n) <= 2cn - c = O(n)。

希望这可以帮到你！

- templatetypedef

Answer 3

主定理是解决这个问题的好方法：

将给定的方程

T(n) = 2T(n/2) + c

与公式

T(n) = aT(n / b) + (n^k log^p n)
其中 a >= 1，b > 1，k >= 0，p 是实数

进行比较，我们可以说它满足条件 a > b^k，因为 a = 2，b = 2，k = 0
所以，T(n) = θ(n^{log _b a}) = θ(n)

- Bikash Pandey