递归算法的时间复杂度

Question

如何计算递归算法的时间复杂度？

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}

Answer 1

分析递归函数(甚至评估它们)是一项非常重要的任务.A(在我看来)好的介绍可以在Don Knuths 混凝土数学中找到.

但是,让我们现在分析这些例子:

我们定义了一个函数,它为我们提供了函数所需的时间.假设t(n)表示所需的时间pow(x,n),即函数的函数n.

然后我们可以得出结论,t(0)=c因为如果我们调用pow(x,0),我们必须检查是否(n==0),然后返回1,这可以在恒定时间内完成(因此常量c).

现在我们考虑另一种情况:n>0.我们在这里获得t(n) = d + t(n-1).那是因为我们再次检查n==1,计算pow(x, n-1,因此(t(n-1)),并将结果乘以x.检查和乘法可以在恒定时间(常数d),pow需求的递归计算中完成t(n-1).

现在我们可以"扩展"这个术语t(n):

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

那么,在我们到达之前需要多长时间t(1)？由于我们从t(n)每个步骤开始减去1,因此需要n-1步骤才能达到t(n-(n-1)) = t(1).另一方面,这意味着,我们得到n-1时间常数d,并t(1)进行评估c.

所以我们得到:

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

所以我们得到的t(n)=(n-1) * d + c是O(n)的元素.

pow2可以使用Masters定理来完成.因为我们可以假设算法的时间函数是单调递增的.所以现在我们有时间t(n)计算pow2(x,n):

t(0) = c (since constant time needed for computation of pow(x,0))

因为n>0我们得到了

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

以上内容可以"简化"为:

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

所以我们得到了t(n) <= t(n/2) + d,可以使用主人定理来解决t(n) = O(log n)(参见维基百科链接中的流行算法应用,例如"二进制搜索").

Answer 2

让我们从pow1开始,因为这是最简单的一个.

你有一个函数,在O(1)中完成一次运行.(条件检查,返回和乘法是恒定时间.)

你剩下的就是你的递归了.您需要做的是分析函数最终调用自身的频率.在pow1中,它会发生N次.N*O(1)= O(N).

对于pow2,它的原理是相同的 - 单个运行的函数在O(1)中运行.但是,这次你每次减半.这意味着它将运行log2(N)次 - 实际上每位运行一次.LOG2(N)*O(1)= O(日志(N)).

可能对你有所帮助的是利用递归总是可以表示为迭代的事实(并不总是非常简单,但它是可能的.我们可以将pow1表达为

result = 1;
while(n != 0)
{
  result = result*n;
  n = n - 1;
}

现在你有了一个迭代算法,你可能会发现以这种方式分析它更容易.

Answer 3

它可能有点复杂,但我认为通常的方法是使用Master's定理.

Answer 4

忽略递归的两个函数的复杂性是O(1)

对于第一算法,pow1(x,n)复杂度为O(n),因为递归深度与n线性相关.

第二个复杂度是O(log n).这里我们大约递归log2(n)次.抛出2我们得到log n.