計算複雜度

當我們想要與其他人寫的演算法去做比較的時候，常常會使用"計算複雜度"以及"空間複雜

度"去做比較，這種比較方法比較科學。  那我們為什麼不用運行時間來比較呢?

很簡單!是因為我們每個人的電腦設備都不同，而該電腦在執行時背後很有可能正在執行其他

的程式，這時也會導致不準確。   舉個例子，A演算法執行在一般的電腦上跑了10秒，但是執

行在超級電腦的B演算法可能連1秒都不到，但是難道可以說B演算法比A演算法好嗎?

懂我的意思嗎?

下面是一個矩陣相加例子:

for(int i=0;i<n;i++){ //n+1

for(int j=0;j<n;j++){ //n(n+1)

MatrixResult[i][j]=MatrixA[i][j]+MatrixB[i][j]; //n²

}

}

for迴圈會執行n+1次，因為當 i=n 時 for 迴圈會進行一次比較，這也算一次。

所以計算複雜度為:  2n²+2n+1  = >  Big-O( n² )

Big-O定義為: f ( n ) = Big-O ( g ( n ) )，若且唯若存在一正整數 c 及 n0

，使得 f ( n ) < = c * g ( n )，對所有的n，n > = n0


根據定義，也就是說

f(n)= 2n^2+2n+1 ; 存在C=3 , n0=3 使得 n>=3後 2n^2+2n+1 <=3n^2 

所以 f(n)=> big-O (n^2)

By   Victor