審判程式的靈魂

                                   算法效率的度量

一:事後統計法

a.比較不同算法對同一組輸入資料的運作處理時間。

缺陷：

a.為了獲得不同算法的運作時間必須編寫相應程式。

b.運作時間嚴重依賴硬體以及運作時的環境因素。

c.算法的測試資料的選取相當困難。

總結:事後統計法雖然直覺，但是實施困難且缺陷多，一般不予考慮。

二:事前分析估算

a.依據統計的方法對算法效率進行估算。

影響算法效率的主要因素：

a.算法采用的政策和方法。

b.問題的輸入規模。

c.編譯器所産生的代碼。

d.計算機執行速度。

function fn_sun(array,len){

var i =0;         1

var j=0; 1

var s=0; 1

for(i=0;i<len;i++){

for(j=0;j<len;j++){

s+=i*j; n*n（關鍵部分）

}

return s;  1

t = (n*n+4)*T;

T:js程式執行代碼時間

啟示:

a.随着問題規模n的增大，它們操作數量的差異會越來越大，是以實際算法在時間效率上的差異性會變得非常明顯!

b.判斷一個算法的效率時，往往隻需要關注操作數量的“最高次項”，其他次要項和常數項可以忽略。

  大O表示法

  a.算法效率嚴重“依賴”于“操作(Operation)數量”。

  b.在判斷時首先關注操作數量的“最高次項”。

  c.操作數量的估算可以作為時間複雜度的估算。

   O(5) = O(1)

   O(2n+1) = O(2n) =O(n)

   O(n*n+n+1) = O(n*n)

   O(3*n*n*n+1) =O(3*n*n*n)= O(n*n*n+1)

 常見的時間複雜度類型:

執行函數           階          非正式術語

12   O(1)            常數階

2n+3              O(n)            線性階

3n*n+2*n_1        O(n*n)          平方價

5log2n+20         O(logn)         對數階

2n+3nlog2n+19     O(nlogn)        nlogn階

6n*n*n+2n*n+3n+4  O(n*n*n)        立方階

2的n次方          O(2的n次方)     指數階

關系:

O(1)<O(logn)<O(n)<O(nlogn)<O(n*n)<O(n*n*n)<O(2的n次方)<

O(n!)<O{n的n次方}

最壞與最好

function search(array,len,n){

var ret =-1;

var i=0;

if(array[i]==n){

ret = i;

break;

return ret;

var array = [1,2,3,4,5];

console.log(search(array,5,1));  最好的情況，複雜度O(1)

console.log(search(array,5,5));  最壞的情況, 複雜度O(n)

意義:

當算法在最壞情況下仍然能滿足需求時，可以推斷，算法的最好情況和平均情況都滿足需求。

空間與時間的政策

a.多數情況下，算法執行時“所用的時間”更令人關注。

b.如果有必要，可以通過增加空間複雜度來降低時間複雜度。

c.同理，也可以通過增加時間複雜度來降低空間複雜度。

注意：

在實作算法時，需要分析具體問題對執行時間和空間的要求。

本文轉自 沉迷學習中 51CTO部落格，原文連結：http://blog.51cto.com/12907581/1951422，如需轉載請自行聯系原作者