我有一个正在尝试实现的算法.我被要求确定一个描述其最坏情况下运行时间的函数.作为输入，它需要一定长度的数组(我们称其为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:

对不起，如果我对实现细节不太了解，但是在某种意义上，它与诸如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.

因为两者都只返回一个数字(一个是对数组的查找，但这也是恒定时间).对于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

因为您评估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.

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

If you look at the values, you see that

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

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.