algorithm - 主定理基本情况是恒定的？

Question

主定理是否假设 T(1) 是常数？假设我有一个时间复杂度的算法：T(n) = 2T(n/2) + O(1) and T(1) = O(logn)，这个算法的时间复杂度是多少？

Answer 1

你的说法T(1) = O(logn)没有任何意义。您基本上说某些由于某种原因不依赖的函数具有对数复杂度（因此以对数方式n依赖）。n

T(1), T(2), T(532143243)是边界条件，不能依赖于任何参数。它们应该是一个数字 ( 5, pi/e, sqrt(5) - i)

Answer 2

对于递归关系：T(n) = 2T(n/2) + O(1)，我们有

• a = 2
• b = 2
• 在递归之外工作的 O(1) 时间成本

因此主定理案例 1 适用，我们有：

T(n) ∈ Θ(n ^ log2(2)) ⇒</p>

T(n) ∈ Θ(n)

递归关系基于初始项定义序列。如果大小为 1 的问题通过递推关系解决T(1) = f(n)，其中 f ∈ O(logn)，则无法确定 T(1) 的值，即作为递推关系没有任何意义。

Answer 3

有时最好只是尝试一下，而不是依赖定理。

T(m) = 2T(m/2) + O(1)
T(1) = O(logn)

T(2) = 2T(1) = 2log(n)
T(4) = 2T(2) = 4log(n)
T(8) = 2T(4) = 8log(n)
T(16) = 2T(8) = 16log(n)
T(32) = 2T(16) = 32log(n)
T(m) = 2T(m/2) = mlog(n)

总之，正如其他人所指出的那样，您最初的问题确实是荒谬的，因为您试图计算T(n)在. 但是我们可以回答您作为评论添加的第二个问题。nT(1) = O(logn)