algorithm - 得到T(n)=T(n/4)+T(3n/4)+c的复杂度

Question

在这个递归关系 T(n)=T(n/4)+T(3n/4)+c 中，我只是混淆了这个递归关系与最佳和最坏情况分析，因为我们必须同时解决大小为 n/4 和 3n/4 的子问题，那么这里最坏情况或最佳情况分析的术语是什么？

此外，我们应该在这里使用 theta(log n ) 我们的 O(log n ) ，虽然看到下面的链接我发现 O(log n ) 更适用但仍然无法理解为什么我们不使用 theta(log n )在这里。

How to solve the recursive complexity T(n) = T(n/4)+T(3n/4)+cn

Answer 1

T(n) = T(n/4) + T(3n/4) + CONST <= 2T(3n/4) + CONST

我们将使用 case 1 of master theorem与:

a = 2, b = 4/3.
c = log_{4/3}(2) ~= 0.4
CONST is in O(n^0.4)

因此，根据主定理，一个计算机辅助设计人员推导出 2T(3n/4) + CONST在Theta(logn) , 自 T(n) <= 2T(3n/4) + CONST ，我们可以说 T(n)在O(logn) .

遵循相同的想法，但有下限:

T(n) >= T(3n/4) + CONST ...

再次使用主定理，我们可以看出 T(n) 也在 Omega(logn) 中.

因为 T(n) 既是 O(logn) 又是 Omega(logn)，所以它也是 Theta(logn)。

---

至于您的问题，您可以使用大 O 或 Theta 表示法，随您喜欢。如您所见，证明 Theta 需要做更多的工作，但它也提供更多信息，因为它告诉您您发现的界限很紧。