递归关系的最坏情况和最佳情况 运行-时间复杂度 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)。

对于best-case的复杂度，需要研究算法在增加尺寸时的行为，分析算法是否有属性可能导致不同的场景。例如，在 BST 中搜索在最佳情况下可能是不变的，但您仍然考虑输入 'n'，而不是使用单个元素的最佳情况。

在你的情况下，你没有具体的算法，而是一个函数（表示为递归）。因此，谈论最好和最坏的情况

没有意义

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

在计算递归时，不仅要考虑递归树的高度，还要考虑分支的数量。因此：

If we look at the worst case complexity, we have

T(n) = n * T(1)

你的理由不正确。