题目——
分析思路——
我的程序——
思路一: 传统的递归方法
然而,这种算法的时间复杂度是 O(2^n)。我是这样计算的,假设找出第n个月兔子总数的算法的复杂度(时间)是T(n),而用一个常量
A来表示找出第1和2个月兔子总数所花费的时间;那么将会有: T(n) = T(n -1)+ T(n - 2) + A; 用高中数列知识解,可知其结果是2^n的数量级的。
思路二——
注意到最新一个月的兔子数量肯定是前两个月的兔子数量的相加。为了避免思路一那样冗余的计算到第一和第二个月的结果,我们每算出一个月的结果便用两个变量来存储前两个月的数目,如此通过相加即可得到最后一个月的数目。
明显,思路二的时间主要地花在了 for (int i = 3; i <=n; i++) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
这个循环里,因此整个程序的时间复杂度是O(n) ,改进了不少。
|
|