该算法最坏的运行时间(如何证明)? [英] Worst case running time of this algorithm (how to justify)?

问题描述

我有一个正在尝试实现的算法.我被要求确定一个描述其最坏情况下运行时间的函数.作为输入，它需要一定长度的数组(我们称其为n).然后它的工作如下:

I have an algorithm i'm trying to implement. I've been asked to determine a function that describes its worst case running time. As input, it takes an array of some length (lets call it n). Then what it does is as follows:

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个，依此类推.我只是不确定如何正式证明这一点

Sorry if I'm a tad sparse on the implementation details, but in a sense, its rather similar to something like the fibbanoci sequence. I'm thinking the worst case running time of this algorithm is t(n)=2^n, because if n is large, it will decompose into 2 separate calculations, which in turn will split into 2 more and so on. I'm just not sure how to formally justify this

推荐答案

让我们首先获得运行时间的递归.

Let's first get a recursion for the running time.

T(0) = T(1) = 1

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

since both just return a number (one is an array-lookup, but that's constant time too). And for n > 1 we have

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

因为您评估f(n-1)和f(n-2)并将两个结果相加.这与斐波那契序列本身F(n) = F(n-1) + F(n-2)的重复率几乎相同，并且结果密切相关.

since you evaluate f(n-1) and f(n-2) and add the two results. That's almost the same recurrence as the Fibonacci sequence itself, F(n) = F(n-1) + F(n-2), and the result is closely related.

 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

如果查看这些值，就会看到

If you look at the values, you see that

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

并可以通过归纳证明这一点.

and can prove that with induction, if you need to.

由于斐波那契数列的项由F(n) = (φ^n - (1-φ)^n)/√5给出，其中φ = (1 + √5)/2，因此您看到f的复杂度也为Θ(φ^n)，就像斐波那契数列一样.这比Θ(2^n)更好，但仍然是指数级的，因此使用这种方法进行的计算仅适用于较小的n.

Since the terms of the Fibonacci sequence are given by F(n) = (φ^n - (1-φ)^n)/√5, where φ = (1 + √5)/2, you see that the complexity of your f is also Θ(φ^n), like that of the Fibonacci sequence. That's better than Θ(2^n), but still exponential, so calculation using this way is only feasible for small n.

这篇关于该算法最坏的运行时间(如何证明)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！