时间复杂度和主定理

Question

我正在尝试更好地理解主定理和时间复杂度。我找到一些在线练习的例子。请问我的答案正确吗？

T(N) = 3T(N/3) + O(N)

时间复杂度为Θ(n)，因为log(base 3) 3 = 1。因此，Θ(n^1) + O(N) 简化为 Θ(n)。

T(N) = 3T(2N/3) + O(1)

我不理解这个。我知道这是傻瓜排序算法，但是如果应用主定理，a和b都是3，那么log（基数3）3 = 1，使得Θ（n）？我知道这是不正确的，但我很难理解主定理。

T(N) = 4T(N/2) + O(N)

时间复杂度为Θ(n^2)，因为log(base 2) 4 = 2。那么，N^(log(base 2) 4) = N^2。

T(N) = 2T(N/2) + O(N log(N))

这里我认为它仅仅是O（N log(N)），因为2的对数（以2为底）为1。

- user3521441

---

第一个情况是O(n log n)；仔细阅读定理。在第二种情况下，b = 3/2。 - G. Bach

你是指四个例子中的第一个吗？你介意解释一下原因吗？ - user3521441

对于 T(n) = 3T(n/3) + O(n)（我假设您指的是最后一个求和项为 Θ(n)），由于 1 = log_3 3，因此定理的第二种情况（根据维基百科）适用，您得到 T(n) = Θ(n log n)。我认为该定理不适用于 T(n) = 2T(n/2) + Θ(n log n)。 - G. Bach

我是指大O而不是大theta。这会有多大的区别？ - user3521441

区别在于当 f = o(n) 时，你会得到 T(n) = Θ(n)，而当 f = Θ(n) 时，你会得到 T(n) = Θ(n log n)。 - G. Bach

Answer 1

根据主定理：

if 
T(n) = aT(n/b) + f(n^k)

if loga/logb > k  then T(n) = O(n^(loga/logb))

if loga/logb < k  then T(n) = O(n^k)

else T(n) = O(n*logn)

 1. a = 3 b = 3 k=0  loga/logb = 1 = k    hence T(n) = O(nlogn)
 2. a = 3 b = 3/2 k=0 log3/log(3/2) > 1 > k  hence T(n) = O(n^(log3/log(3/2)))
 3. a = 4 b = 2 k = 1 log4/log2 = 2 > 1  hence T(n) = O(n^2)

- Vikram Bhat

---

好的，你的解释比我看到的其他解释更有帮助。但是第四个怎么工作，因为f(x)不是以(n^k)形式而是以f(x) = N log N形式？ - user3521441

@VikramBhat 这是错误的；虽然 n log n 在 n 的小欧米伽中，但主定理在这里不适用。第四个问题的正确答案是 n log^2 n。 - G. Bach

Answer 2

首先让我们详细阐述主定理并分析您的四种情况。

在上面的图片中，它显示每个级别的复杂度是：

然后我们将所有层次的计算结果相加，得到总和：

然后我们只需要分析总函数，它是一个几何级数，并由乘法因子（或公比）a/b^d确定。

1. 如果公比大于1，则会朝着最后一项呈指数增长：
   当 a/b^d > 1 或 d<log_b a 时，这是大O。

2. 如果公比小于1，则从主导项 n^d 开始呈指数衰减，即当 a/b^d < 1 或 d > log_b a 时，这是大O。

3. 如果公比等于1，则序列将是一个常数序列，我们对所有项求和：
   

---

在您的情况1中，其中T(N) = 3T(N/3) + O(N)，我们首先看到公比a/b^d = 3/3^1=1。

而对于您的情况2T(N) = 3T(2N/3) + O(1)，它将是a/b^d = 3/(3/2)^0 = 3 > 1（其中a = 3，b = 3/2和d = 0），因此大O将是：。

对于您的情况3T(N) = 4T(N/2) + O(N)，a将为4，b将为2，d将为1。

对于你的第四个案例 T(N) = 2T(N/2) + O(N log(N))，公比会小于1，因为 a/b^d = 2/2^1.x，其中 d > 1，所以几何级数将呈指数衰减。因此，第一项 n log n 将支配该级数，因此它将成为大O。

参考文献：

1. https://www.coursera.org/learn/algorithmic-toolbox

- Lerner Zhang