得到T(n)=T(n/4)+T(3n/4)+c的复杂度
Get the complexity of T(n)=T(n/4)+T(3n/4)+c
在这个递归关系 T(n)=T(n/4)+T(3n/4)+c 中，我只是混淆了这个递归关系与最佳和最坏情况分析的关系是什么，因为我们必须解决两个子问题，这两个子问题的大小n/4 和 3n/4 那么最坏情况或最佳情况分析的术语是什么？
此外，我们应该在这里使用 theta(log n ) 我们的 O(log n ) ，虽然看到下面 link 我发现 O(log n ) 更适用但仍然无法理解为什么我们不这样做在此处使用 theta(log n)。
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)在[=17中=].
遵循相同的想法，但下限为：
T(n) >= T(3n/4) + CONST ...
再利用主定理，我们可以看出T(n)也在Omega(logn).
因为T(n)既是O(logn)又是Omega(logn)，所以它也是Theta(logn)。
至于你的问题，你可以使用大 O 或 Theta 表示法，随你喜欢。如您所见，证明 Theta 需要做更多的工作，但它也提供更多信息，因为它告诉您发现的界限很紧。
这些类型的重复可以用 Akra-Bazzi 定理轻松解决（如果您查看了您链接的问题，有人向您展示了类似问题的解决方案）。
所以 1/4^p + (3/4)^p = 1，其中 p = 1。在你的情况下 g(u) = c，所以积分
因此 1 to x 中的 int c/u^2 du 等于 1 to x 中的 -1/u。这等于 -1/x + 1。现在，当你将它乘以 x 时，你会得到复杂度是 O(n) 而不是其他人建议的 O(log n)。
在这个递归关系 T(n)=T(n/4)+T(3n/4)+c 中，我只是混淆了这个递归关系与最佳和最坏情况分析的关系是什么，因为我们必须解决两个子问题，这两个子问题的大小n/4 和 3n/4 那么最坏情况或最佳情况分析的术语是什么？
此外，我们应该在这里使用 theta(log n ) 我们的 O(log n ) ，虽然看到下面 link 我发现 O(log n ) 更适用但仍然无法理解为什么我们不这样做在此处使用 theta(log n)。
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)在[=17中=].
遵循相同的想法，但下限为：
T(n) >= T(3n/4) + CONST ...
再利用主定理，我们可以看出T(n)也在Omega(logn).
因为T(n)既是O(logn)又是Omega(logn)，所以它也是Theta(logn)。
至于你的问题，你可以使用大 O 或 Theta 表示法，随你喜欢。如您所见，证明 Theta 需要做更多的工作，但它也提供更多信息，因为它告诉您发现的界限很紧。
这些类型的重复可以用 Akra-Bazzi 定理轻松解决（如果您查看了您链接的问题，有人向您展示了类似问题的解决方案）。
所以 1/4^p + (3/4)^p = 1，其中 p = 1。在你的情况下 g(u) = c，所以积分
因此 1 to x 中的 int c/u^2 du 等于 1 to x 中的 -1/u。这等于 -1/x + 1。现在，当你将它乘以 x 时，你会得到复杂度是 O(n) 而不是其他人建议的 O(log n)。