29

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

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;
    }
}
4

5 回答 5

37

分析递归函数（甚至评估它们）是一项不平凡的任务。（在我看来）一个很好的介绍可以在 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 theorem来完成。因为我们可以假设算法的时间函数是单调递增的。所以现在我们有了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，这可以使用 masters theorem 来解决t(n) = O(log n)（参见维基百科链接中流行算法的应用部分，例如“二进制搜索”）。

于 2010-04-25T17:42:32.950 回答
12

让我们从 pow1 开始，因为这是最简单的。

您有一个在 O(1) 中完成单次运行的函数。（条件检查、返回和乘法是常数时间。）

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

对于 pow2，原理相同——函数的单次运行在 O(1) 中运行。但是，这一次你每次都将 N 减半。这意味着它将运行 log2(N) 次 - 每比特有效一次。log2(N)*O(1)=O(log(N))。

可能对您有所帮助的是利用递归始终可以表示为迭代这一事实（并不总是非常简单，但它是可能的。我们可以将 pow1 表示为

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

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

于 2010-04-25T17:28:56.223 回答
6

它可能有点复杂，但我认为通常的方法是使用Master's theorem。

于 2010-04-25T17:25:32.260 回答
5

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

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

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

于 2010-04-25T17:25:50.073 回答
0

所以我猜你正在将 x 提高到 n 次方。pow1 需要 O(n)。

您永远不会更改 x 的值，但每次从 n 中取 1 直到它变为 1（然后您只需返回）这意味着您将进行 n 次递归调用。

于 2010-04-25T17:28:44.070 回答