資料結構中大O時間複雜度推論

   大O時間複雜度的推導原則有三條:

       1.你推導到的所有時間複雜度相加的常數全部去掉,然後将去掉後的值+1;

       2.隻保留去掉後複雜度的最高階,如果有最高階存在的話;

       3.去掉與最高階相乘的常量,如果有最高階的話!

下面我們根據大O推導法,結合我們程式中經常遇到的情況,推導一下時間複雜度(以java代碼為例):

1.public void cal(){     int i=0; //執行一次    System.out.println(i);// 執行一次    System.exit(0);   //執行一次 } 上面的代碼中總執行次數為:1 + 1 + 1. (1)根據大O推導方法第一條,将所有常量去掉,然後加1,得到最後的結果1; (2)因為第一步中的1，沒有最高階，是以第二條和三條原則均不适用.是以最後結果為1.用大O表示法表示為O(1).

2.public void cal(){            int i = 0;  //執行一次           for(ini i = 0;i < n;i++){             System.out.println(i); //執行n次         }     }     上面的代碼中執行次數為: 1 + N;     (1)根據大O推論第一條,去掉所有常量後再加1,還是1 + n;     (2)根據第二條,隻保留最高階,(n的一次方,也算階),則去掉1,隻剩下n;    (3)根據第三條,因為沒有與N相乘的常量,是以最後結果還是n;用大O表示法即為O(n)。

3.public void cal() {    int i = 0; //執行一次    for(int i = 0;i < n;i++) {       i = i * 2; //執行次數大緻是n的一半時間    } } 上面的代碼中,由于受常量2的影響,是以執行次數為1 + 2 的X次方(X為執行次數),則2的x次方等于n,得到x = log2N;是以最後的執行次數為 1 +log2N; (1)根據第一條原則,去掉所有常量,後再加1,還是1 + log2N; (2)根據第二條原則,隻保留最高階,則去掉1,變為log2N; (3)根據第三條原則,去掉與最高階相乘的常量後為logN,是以最後結果    為O(logN);

4.public void cal(){       int i = 0;j = 0; //執行一次      for(i = 0;i < n;i++) {         for(j = 0;j < n;j++) {            System.out.println(j);        }     } } 上面的代碼執行次數為1 + n * n即為1 + n2; (1)根據第一條原則,結果還是1 + n2; (2)根據第二條原則,隻保留最高階，結果為 n2; (3)根據第三條原則,因為沒有與最高階相乘的常量,是以最後結果為: n2,表示為:O(n2);

5.public void cal(){       int i = 0;j = 0; //執行一次      for(i = 0;i < n;i++) {         for(j = 0;j < M;j++) {            System.out.println(j);        }     } } 上面代碼的執行次數為1 + n * m; (1)根據第一條原則,還是1 + n * m; (2)根據第二條原則,去掉所有常量,保留最高階,變為n*m; (3)根據第三條原則,去掉與最高階相乘的常量,因為沒有相乘的常量,是以最終結果還是n * m,表示為O(n*m);

6.public void cal(){       int i = 0;j = 0; //執行一次      for(i = 0;i < n;i++) {         for(j = i;j < n;j++) {            System.out.println(j);        }     } } 注意上面的代碼中j初始值為i,是以推導相對複雜一些,當i =1時,執行了執行了n*(n - 1)次,當i =2時,執行了n*(n -2)次,其它以此類推,我們以執行二次為例來推導,該為n*(n -1) + n*(n - 2),則最後的結果為n*n - n + n*n -2n即為2n2-3n; (1)根據第一條原則,因為沒有相加的常量,是以結果為2n2-3n; (2)第二條原則,隻保留最高階,結果為2n2; (3)第二條原則,去掉與最高階相乘的常量,結果為n2,是以最後結果即為n2,表示為O(n2);

以上即為我們程式中常見代碼的時間複雜度的推論方式.