分析下面这个简单的例子将帮助你把握这种技巧的使用方法: #include <stdio. h> #include <stdlib. h> /* * Declare the functions that the main function is using */ int A(), B(int), C(int, int); /* * The main PRogram */ int A(), B(), C(); /*These are functions in some other module * / int main() { int v1, v2, v3; v1 = A(); v2 = B(v1); v3 = C(v1, v2); printf ("The Result is %d. /n" , v3); return(0) ; }
从表面上看,上述程序段是定义菲波那契数的一种很简单的方法。这段程序简洁短小,看上去执行时间不会太长。但事实上,哪怕是用计算机计算出较小的菲波那契数,例如第100个,都会花去很长的时间,下文中将分析其中的原因。 假如你要计算第40个菲波那契数的值,就要把第39个和第38个菲波那契数的值相加,因此需要先计算出这两个数,而为此又要分别计算出另外两组更小的菲波那契数的和。不难看出,第一步是2个子问题,第二步是4个子问题,第三步是8个子问题,如此继续下去,结果是子问题的数目以步数为指数不断增长。例如,在计算第40个菲波那契数的过程中,函数fib()将被调用2亿多次!即便在一台速度相当快的计算机上,这一过程也要持续好几分钟。 数字的排序所花的时间有时也会超出你的预料: /* * Routine to sort an array of integers. * Takes two parameters: * ar---The array of numbers to be sorted, and * size---the size of the array. */ void sort( int ar[], int size ) { int i,j; for( i = 0; i<size - 1; ++ i) { for( j = 0; j< size - 1; ++j ) {