演算法效能分析

演算法效能(performance)從所需時間及所需記憶體空間來評估。
執行時間長短一般以時間複雜度(Time complexity)表示。

時間複雜度

設n為資料輸入量，T(n)為程式執行所要花費時間，f(n)為執行時間成長率，若存在兩個常數c與n0，若n>=n0，則T(n)<=cf(n)，則T(n)之時間複雜度為O(f(n))(讀成order is f(n))，其涵義為某演算法T在電腦中所需執行時間不會超過f(n)的某一常數倍。
例：

$T(n)=n^3 + 2n^2 +5$，求時間複雜度?
Solution
需找出c、n0及f(n)，

Step1. 已知T(n)之最高階次為 ，因此假設
Step2. 同時要找出c、n0，使T(n)<=cf(n)，因T(n)中有5n，因此n必須大於0，故n0=0
Step3. 當c=10, 可推得

Step4. Time complexity = O(n3)

Best, Worst, and Average Cases

https://en.wikipedia.org/wiki/Best,_worst_and_average_case 演算法都有三種可能發生之情形. 1. 最佳情形(Best Case) 2. 平均情形(Average Case) 3. 最差情形(Worst Case)

以插入排序演算法來說： 1.將資料分成已排序、未排序兩部份 2.依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置 3.插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入 4.比較時，若遇到的值比正處理的值大或相等，則將值往右移

int data[20];
int length = 20;
int i, j, tmp;
for(i = 1; i < length; i++){
    tmp = data[i];
    for( j=i; j > 0 && tmp < data[j-1]; j-- )
        data[j] = data[j-1];        
    data[j] = tmp;
}

時間複雜度(Time Complexity) 1.Best Case：Ο(1) 當資料的順序恰好為由小到大時，每回合只需比較1次 2.Worst Case：Ο(n2) 當資料的順序恰好為由大到小時，第i回合需比i次 3.Average Case：Ο(n2) 第n筆資料，平均比較n/2次

排序時間複雜度(Time Complexity)