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

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 ) 花费一个时间单位到 return 在 [0, n] 范围内均匀分布的随机整数值，而所有其他指令花费的时间都可以忽略不计（例如，T(0) = 0）。

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

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，您可以通过伸缩级数来推导出它，或者通过猜测解然后代入它来证明它有效。

Computing expected time complexity of recursive program