Question

递归和非递归算法求解Fibonacci数列

Answer 1

对于Fibonacci数列

我们可以采用递归以及非递归的方法对其进行求解。

下面分别用两种方法求解，并分析算法的时间复杂度。

输入 时，

输入 时，

假设 时 ， 正确,

当 时， 正确。

So the correctness of Algorithm has been proved.

对于 来说，每个问题被分成了两个子问题。每分割一次，问题的规模线性减少。

对于每个节点来说，每个节点对应算法执行一次操作的时间复杂度为 。

二叉树的总层数为 , 所以我们可以近似认为

下面给出具体分析：

对于 :

尾部常数 4 代表 四次常数操作 (1 comparison, 2 subtractions, 1 addition)

我们可以发现 , 代入得：

所以lower bound我们说，

我们认为 ， 因为

可得：

我们可以发现 , 代入得：

所以对upper bound我们说，

综上，该算法时间复杂度

首先，为A[0], A[1]赋值分别需要两个 的操作。

对于循环部分，时间复杂度为 。

所以

综上，迭代方法求解Fibonacci的时间复杂度为

最初发布在我的 个人博客 上。欢迎访问。