在这个递推关系中，我只是混淆了这个递推关系与最佳和最坏情况分析之间的关系，因为我们必须同时解决大小为n/4和3n/4的子问题，那么这里最坏情况或最佳情况分析的术语是什么？
此外，我们应该在这里使用θ（log n）我们的o（logn），虽然看到下面的链接，我发现o（logn）更适用，但仍然无法理解为什么我们不在这里使用θ（logn）。
How to solve the recursive complexity T(n) = T(n/4)+T(3n/4)+cn
最佳答案
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)
因此，从主定理，一个cad导出
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）又是ω（logn），所以它也是θ（logn）。
至于你的问题，你可以使用大O或θ符号，无论你喜欢什么如你所见，证明θ需要更多的工作，但它也更具信息性，因为它告诉你，你发现的界限很紧。
关于algorithm - 获得T(n)= T(n/4)+ T(3n/4)+ c的复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34474219/