algorithm - 循环关系的最坏情况和最佳情况运行时复杂度 T(n) = 2T(n/2) + T(n-1) + 常数

Question

我正在寻找以下递归关系的最坏情况和最佳情况运行时分析:

T(n) = 2T(n/2) + T(n-1) + 1

我在 Stack Overflow 或 Web 上找不到严格相同的问题。
在这种情况下，我们有三个分支，我们知道 T(n/2)将比 T(n-1) 更快地达到基本情况会，所以根据我的理解，最长的叶子到根路径代表最坏情况的复杂性，最短的叶子到根路径代表最好的复杂性。
因此，我们认为最好的情况复杂度是:

T(n) = log(n) * T(1)

假设 T(1)=1 ，那么我们有最佳情况复杂度

T(n) = O(logn)

如果我们看一下最坏情况的复杂性，我们有

T(n) = n * T(1)

所以，那么我们有(再次假设 T(1)=1):

T(n) = O(n)

我可能在这里误解了什么，或者这个时间分析对于这种递归关系是否准确？

Answer 1

Assuming that T(1)=1, then we have best-case complexity

您不能简单地替换 T(1)并声称它是最佳情况的复杂性。特别是使用 Big-O 表示法来表示

T(n) = O(logn)

要正确，您将使用 Ω(logn) .
对于最佳情况复杂度，需要研究算法在增加大小时的行为，并分析是否存在可能导致不同场景的算法属性。例如，在最佳情况下，在 BST 中搜索可以是恒定的，但您仍然使用输入 'n' 来考虑它，而不是使用单个元素的最佳情况。
在您的情况下，您没有具体的算法，而是一个函数(表示为循环)。因此，谈论最好和最坏的情况是没有意义的

In this case, we have three branches, and we know that T(n/2) wouldreach the base case faster than T(n-1) would, so from myunderstanding, the longest leaf to root path represents the worst-casecomplexity

在计算递归时，不仅要考虑递归树的高度，还要考虑分支的数量。所以:

If we look at the worst case complexity, we have

T(n) = n * T(1)

你的理性不正确。