|
题目:古典题目,有一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假设所有的兔子都不死，问每个月的兔子总数为多少。对应的数列就是斐波那契(Fibonacci)数列。斐波那契数列为：0、1、1、2、3、……，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) （当n>1时）。 1.递归算法：最好理解的算法,与定义公式十分吻合，和人的思路相当接近,对应的数学描述很清晰，容易编程；计算过程存在大量重复的运算，时间复杂度达到了O(2^n)，使用的内存空间也随着函数调用栈的增长而增长。这显然不适于实用的程序。 unsigned long Fibonacci(int n) { if (n <= 1) { return n; } else { return Fib(n - 1) + Fib(n - 2); } }2.循环函数算法：Fibonacci数列的规律就是不停的赋值，计算第n项时虽然要用到前面两项的值，但它们仅作为临时计算的中间值，不作为结果输出，因此无保留的必要，完全可以转化成循环函数法求解。循环函数法的时间复杂度为O(n)，使用的内存空间也不会动态上涨。个人认为Fibonacci数列更适宜作为迭代法而非递归法的典例出现在教材上。 unsigned long Fib(int n) { int i; unsigned long a = 0, b = 1, c; if (n <= 1) { return n; } else { for (i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return c; } }
3.表驱动的递归法：这里不提纯粹的表驱动法，因为对于项数未知的Fibonacci数列开启大片的空间来换取时间未免不值得且不负责。我们只是为了消除递归法中大量重复的运算，可以将已经计算过的中间值存入一个表，已备后续使用。当n小于保存的表长时，由于每个中间值只计算一次，时间复杂度降为O(n)。但随着n的增大，要想维持O(n)的时间复杂度，就必须扩大保存的表长，这就造成了存储空间的浪费。 #define MAX_LOG 20 static unsigned long Logs[MAX_LOG] = {0}; unsigned long Fib(int n) { if (n <= 1) { return n; } else if (n < MAX_LOG && Logs[n] != 0) { return Logs[n]; } else { Logs[n] = Fib(n - 1) + Fib(n - 2); return Logs[n]; } }
时间复杂度：假设某算法的计算时间是f(n)，其中变量可以是输入或输出量，也可以是两者之和或者其他可以计算时间的元素，一般以运算使用次数作时间，那么如果这个算法在某台机器上运行时，所用的时间总是n、n2、2n、logn、n!、nm这些常量函数的一个常数倍，那么就说这个算法的时间复杂度对应的是n、n2、2n、logn、n!、nm。这些常量函数为n、n的平方、2的n次方、log n、n的阶乘、n的m次方.如果这个算法的时间复杂度不能跨越数量级而只是成倍数增长，比如算法a的时间复杂度是n，算法b的时间复杂度是2n，那么这两个算法的时间复杂度都是n。在各种算法中，O(n)表示时间复杂度为n，其他类似。O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)<O(nn)
阅读全文(2192) | 回复(0) | 编辑 | 精华
|
