algorithm - 假设递归函数的递归关系

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

您要做的第一件事是写出指定运行时间的方程式(这通常很简单，不涉及任何求解)。在您的示例中，您用 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)、...:

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)似乎很容易(您可以通过归纳法证明公式，或者只是说“很明显”)。