分析下面這個簡單的例子將幫助你把握這種技巧的使用方法: #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 ) {