最坏的情况下这个算法的运行时间(如何证明)？

Question

我有一个算法,我正在尝试实现.我被要求确定一个描述最坏情况下运行时间的函数.作为输入,它需要一些长度的数组(让我们称之为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个,依此类推.我只是不确定如何正式证明这一点

Answer 1

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

T(0) = T(1) = 1

因为两者都只返回一个数字(一个是数组查找,但这也是常数时间).对于n > 1我们有

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

因为您评估f(n-1)并f(n-2)添加了两个结果.这与Fibonacci序列本身几乎相同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.