实验2：斐波那契数计算
1.实验目的：
掌握分冶策略的基本思想，用分冶法解决问题的一般技巧。
2.实验内容：
参见本实验配套课件pdf文档，实现斐波那契数f(n)的三种算法：(1) 基于定义的递归算法； （2）动态规划（迭代算法）；（3）分治算法（非递归版本）的实现。
3.实验要求：
编制程序并对其时间复杂度和空间复杂度进行分析。测试随着 n 增加各个算法实现的实际运行时间 。
\square 基础性实验 \square 综合性实验 \boxtimes 设计性实验
实验报告正文
一、问题分析（模型、算法设计和正确性证明等）
-
基于定义的递归算法
-
根据Fibonacci定义可得递归表达式：
$$
$$ -
动态规划（迭代算法）
-
先解决小规模问题，并讲解保存起来，利用小规模问题的解构造更大规模问题的解。
当n=0或n=1时，直接返回n；
当n \geq 2时从0,1开始递推计算结果。
-
分治算法（非递归）
-
根据Fibonacci定义可构造如下等式
$$
$$使用二维矩阵表示上述关系
$$
$$将上式推广，则有
$$
$$要求解的Fib(n)即为向量
的第一个分量。
二、算法设计复杂度分析（伪代码，不要粘贴源码）
-
基于定义的递归算法
下求解递归算法时间复杂度下求解递归算法的时间复杂度，设规模为n问题所需的计算时间为T(n)，则有：
$$
$$通过微分方程法求得方程的解：
$$
$$下讨论递归算法的空间复杂度，每次返回函数本身都会开辟新的栈空间，故递归树的高度即为该算法所用空间。递归出口为1和0，递归树高度为n，所以空间复杂度为\theta (n)。
-
动态规划（迭代算法）
下讨论动态规划算法的时间复杂度，设规模为n的问题所需的计算时间为T(n)，则有：
$$
$$下讨论动态规划算法的空间复杂度，该算法仅使用两个整型变量（伪代码中a,b）辅助运算，故空间复杂度为
，或称in place。
-
分治算法（非递归）
下讨论分治算法的时间复杂度，其中矩阵乘法
和
时间复杂度均为O(1)。
设规模为n的问题所需的计算时间为T(n)，则有时间复杂度递归表达：
$$
$$$$
$$考虑该算法空间复杂度，仅使用两个固定大小的矩阵（数组）辅助运算，故空间复杂度为\theta(1)，或称in place。
三、实验结果记录和分析（测试向量上的测试结果、运行时间）
三种算法结果一致，以下显示部分运行结果，其中递归算法在有限时间内（10s）只能计算n\leq46的结果。
| Fibonacci位数 | Fibonacci数 |
|---|---|
| 1 | 1 |
| 6 | 8 |
| 11 | 89 |
| 16 | 987 |
| 21 | 10946 |
| 26 | 121393 |
| 31 | 1346269 |
| 36 | 14930352 |
| 41 | 165580141 |
| 70 | 117669030460994 |
| 80 | 14472334024676220 |
-
基于定义的递归算法
Fibonacci位数 运行时间（ms） 1 0.0002 6 0.0001 11 0.0006 16 0.0055 21 0.0594 26 0.6619 31 7.3609 36 83.4256 41 922.788 46 10249.3 51 113661 -
-
动态规划（迭代算法）
Fibonacci位数 运行时间（ms） 1 0.0003 10 0.0001 100 0.0002 1000 0.0017 10000 0.0163 100000 0.1632 1000000 1.7389 10000000 17.2346 100000000 170.5181 1000000000 1722.873 
-
分治算法（非递归）
Fibonacci位数 运行时间（ms） 1 0.0003 10 0.0004 100 0.0004 1000 0.0005 10000 0.0007 100000 0.0008 1000000 0.001 10000000 0.001 100000000 0.0012 1000000000 0.0013 
四、总结（可描述出现的问题和解决方法、经验和反思等）
在本实验中，分治算法运算时间较快，\theta(log_2n)的复杂度随问题规模增加，运行时间变化较小，难以测量。因此本实验选择运算速率相对较慢的python语言运行相同程序，得到结果相对易于测量观察。
本实验中，通过不断对求解斐波那契数的算法进行优化，我总结如下：
-
递归是方便的算法，编写程序只需考虑求解问题的一部分或是小规模问题，即可运算得到正确结果，无需考虑具体计算过程。但是递归树节点的大量重复很难避免，于是考虑运算过后将小问题的结果储存，求解大问题时直接取出计算。这个过程类似动态的设置递归出口，即不断增加递归出口，从而达到给递归树剪枝的目的来避免重复计算或是每次递归到底层出口，而代价是辅助空间需要相应增加（本实验相对特殊，由于Fibonacci数的特性几乎无需辅助空间）。当递归算法完全转化为“动态设置递归出口”的算法后，不妨从最开始的递归出口考虑问题，将求解大问题需要的小问题答案提前计算储存，即动态规划算法。
-
分治算法在本实验中主要体现在矩阵快速幂，矩阵的使用将Fibonacci数的计算方法完全转化为数学表达，且避开了通项公式中程序不擅长的小数计算。