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

对于Fibonacci数列 \[ F(n)=\left\{ \begin{array}{aligned} 1 && n=0,1 \\ F(n-1)+F(n-2) && n>1 \end{array} \right. \] 我们可以采用递归以及非递归的方法对其进行求解。

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

递归方法

伪代码：

# INPUT N
# OUTPUT Fibonacci数列的第N项数
Fibonacci(N):
	if N <= 1:
		return 1
	else
	 return Fibonacci(N - 1) + Fibonacci(N - 2)

正确性检测：

输入 $N = 2$时，

$Fibonacci(2) = Fibonacci(1) + Fibonacci(0) = 1 + 1 = 2$

输入 $N = 3$时， \[ \begin{aligned} Fibonacci(3) &= Fibonacci(2) + Fibonacci(1) \\ &= Fibonacci(1) + Fibonacci(1) + Fibonacci(1) \\ &= 2 + 1 + 1 = 2 \end{aligned} \] 假设$N = m$时，$Fibonacci(m)$正确,

当$N = m + 1$ 时， $Fibonacci(m + 1) = Fibonacci(m) + Fibonacci(m -1)$ 正确。

So the correctness of Algorithm has been proved.

时间复杂度分析：

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

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

二叉树的总层数为$N-1$, 所以我们可以近似认为$T(n)=O(2^{N-1}) \sim O(2^N)$

下面给出具体分析：

Lower Bound

对于$n>1$:

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

尾部常数 4 代表四次常数操作 (1 comparison, 2 subtractions, 1 addition) \[ \begin{equation} \begin{aligned} T(n) &= T(n-1) + T(n-2) + c \\ &= 2T(n-2) + c \ \ //T(N-1) \sim T(N-2)\\ &= 2*(2T(n-4) + c) + c\\ &= 4T(n-4) + 3c \\ &= 8T(n-6) + 7c \\ &= 2^k * T(n - 2k) + (2^k - 1)*c \end{aligned} \end{equation} \] 我们可以发现$ k = n / 2$, 代入得： \[ \begin{aligned} T(n) &= 2^{n/2} * T(0) + (2^{n/2} - 1)*c \\ &= 2^{n/2} * (1 + c) - c \\ \end{aligned} \] 所以lower bound我们说，$T(n) \sim O(2^{n/2})$

Upper Bound

我们认为 $T(n-2) \sim T(n-1)$，因为 $T(n-2) ≤ T(n-1)$

可得： \[ \begin{aligned} T(n) &= T(n-1) + T(n-2) + c\\ &= 2T(n-1) + c\\ &= 2*(2T(n-2) + c) + c\\ &= 4T(n-2) + 3c\\ &= 8T(n-3) + 7c\\ &= 2^k * T(n - k) + (2^k - 1)*c \end{aligned} \] 我们可以发现$ k = n$, 代入得： \[ \begin{aligned} T(n) &= 2^n * T(0) + (2^n - 1)*c \\ &= 2^n * (1 + c) - c \end{aligned} \] 所以对upper bound我们说，$T(n) \sim O(2^{n})$

综上，该算法时间复杂度 $T(n) = O(2^{n})$

非递归方法

伪代码：

# INPUT N
# OUTPUT Fibonacci数列的第N项数
Fibonacci(N):
	A[0] = 1
	A[1] = 1
	for i = 2 to N - 1:
		A[i] = A[i - 1] + A[i - 2]
	return A[N - 1]

时间复杂度分析：

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

对于循环部分，时间复杂度为 $O((n-1)-2) = O(n-3) \sim O(n)$。

所以 $T(n) = O(n)+O(1)+O(1)$

综上，迭代方法求解Fibonacci的时间复杂度为 $O(n)$