计算递归程序的预期时间复杂度

Question

我希望确定递归算法的平均处理时间T(n)：

int myTest( int n ) {
  if ( n <= 0 ) {
    return 0;
  }
  else {
    int i = random( n - 1 );
    return myTest( i ) + myTest( n - 1 - i );
  }
}

假设算法random(int n)花费一个时间单位来返回在[0，n]范围内均匀分布的随机整数值，而所有其他指令花费极小的时间（例如T(0)=0）。

这显然不是简单形式的T(n) = a * T(n/b) + c，所以我不知道如何编写它。由于每次从0到n-1范围内取一个随机数并将其两次提供给函数并要求这两个调用的求和，因此我无法弄清楚如何编写它。

- mahieyin-rahmun

Answer 1

递归关系为：

T(0) = 0
T(n) = 1 + sum(T(i) + T(n-1-i) for i = 0..n-1) / n

第二个可以简化为：

T(n) = 1 + 2*sum(T(i) for i = 0..n-1) / n

乘以n：

n T(n) = n + 2*sum(T(i) for i = 0..n-1)

注意到 (n-1) T(n-1) = n-1 + 2*sum(T(i) for i = 0..n-2)，我们得到：

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

或者：

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

这个问题的解是 T(n) = n，你可以通过望远镜级数或猜测解并将其代入以证明它有效来推导出它。

- Paul Hankin

---

根据规范，我确定T(0)是存在的。但是当你从步骤1转到步骤2时，你假设对于i>0，T(i)的值也存在。我们如何证明这一点？因为如果它是无限的，那么证明的以下步骤就没有依据了。 - fjardon

@fjardon 没有无限大——代码是这样编写的，递归调用总是在较小的输入上进行，从而限制了调用堆栈的高度。也就是说，如果 myTest(n) 调用 myTest(i)，那么 0 <= i < n。 - Paul Hankin

@Paul，你能解释一下我们是如何得到这一步的吗？n T(n) = (n-1) T(n-1) + 1 + 2T(n-1) = (n+1) T(n-1) + 1。我不太理解。 - mahieyin-rahmun

省略的步骤是将nT(n)重新排列如下：nT(n) = n + 2sum(T(i) for i = 0..n-1) = n-1 + 2sum(T(i) for i = 0..n-2) + 1 + 2T(n-1)。然后注意到n-1 + 2sum(T(i) for i = 0..n-2)等于(n-1)T(n-1)。 - Paul Hankin

@PaulHankin 感谢您的澄清。 - mahieyin-rahmun