1

我有一个我正在尝试实现的算法。我被要求确定一个描述其最坏情况运行时间的函数。作为输入，它需要一个一定长度的数组（我们称之为 n）。那么它的作用如下：

if (n==0){ return 0;}
else if(n==1){return A[0];}
else{
     return f(n-1)+f(n-2)
}

对不起，如果我对实现细节有点稀疏，但从某种意义上说，它与 fibbanoci 序列之类的东西非常相似。我在想这个算法的最坏情况运行时间是 t(n)=2^n，因为如果 n 很大，它会分解成 2 个单独的计算，然后又会分解成 2 个，依此类推。我只是不确定如何正式证明这一点

4

1 回答 1

5

让我们首先得到一个运行时间的递归。

T(0) = T(1) = 1

因为两者都只返回一个数字（一个是数组查找，但这也是常数时间）。因为n > 1我们有

T(n) = T(n-1) + T(n-2) + 1

因为您评估f(n-1)并f(n-2)添加两个结果。这与斐波那契数列本身几乎相同F(n) = F(n-1) + F(n-2)，并且结果密切相关。

 n | T(n) | F(n)
----------------
 0 |   1  |   0
 1 |   1  |   1
 2 |   3  |   1
 3 |   5  |   2
 4 |   9  |   3
 5 |  15  |   5
 6 |  25  |   8
 7 |  41  |  13
 8 |  67  |  21
 9 | 109  |  34
10 | 177  |  55
11 | 287  |  89

如果您查看这些值，您会发现

T(n) = F(n+2) + F(n-1) - 1

如果需要，可以通过归纳证明这一点。

由于斐波那契数列的项由 给出F(n) = (φ^n - (1-φ)^n)/√5，其中φ = (1 + √5)/2，您会看到您的复杂度f也是Θ(φ^n)，就像斐波那契数列一样。这比 好Θ(2^n)，但仍然是指数的，所以使用这种方式的计算只适用于小的n。

于 2012-09-29T19:46:42.720 回答