假设递归函数的递归关系

Question

求递归程序的时间复杂度的方法是什么？我们以这段代码为例。

int hypo(int a, int n) 
{ 
     if(n == 1) 
         return 0; 
     else 
         return a + hypo(a,n-1) * hypo(a,n-1); 
}

Answer 1

这种形式的大多数简单问题都可以用主定理解决。参见 http://en.wikipedia.org/wiki/Master_theorem。

更复杂的问题存在更复杂的方法。 :-)

Answer 2

您要做的第一件事是写出指定运行时间的方程（这通常很简单，不涉及任何求解）。在您的示例中，您用 f(a, n) 表示参数 a 和 n 的函数的运行时间，然后：

f(a, n)不依赖于a，所以我们写成f(n)代替
f(1)是常数；让我们用 k
如果n > 1，则f(n) = c + 2 * f(n-1)，其中c是常数（另一个）

所以现在你需要找出哪个函数满足方程f(n) = c + 2 * f(n-1)和f(1) = k。没有通用方法，但在您的情况下很容易计算 f(2)、f(3)、...:[=27=]

f(2) = c + 2 * f(1) =      c +  2 * k
f(3) = c + 2 * f(2) =  3 * c +  4 * k
f(4) = c + 2 * f(3) =  7 * c +  8 * k
f(5) = c + 2 * f(4) = 15 * c + 16 * k

这里好像很容易找到f(n)（你可以用归纳法证明公式，或者直接说"it's obvious"）。

假设递归函数的递归关系

Recurrence relation for a hypothetical recursive function

algorithm

recursion

time-complexity