The Performance of Your Algorithm
在學習演算法之前，我們通常需要先來了解如何計算一個演算法的效能，演算法通常會由許多的”變數”, ”迴圈”及”判斷式”來組成，而又可以將這三種分為兩類：
1. 影響空間(記憶體) — 空間複雜度：變數(各種資料結構, Ex : List, Array, Map, ArrayList, Dictionary, etc.)
2. 影響時間 — 時間複雜度：迴圈, 判斷式
這兩件事情也是我們程式設計師最要求的兩件事(當然，bug 也最好不要出現)，既要執行有效率又要不佔記憶體，簡直就是要馬兒好又要馬兒不吃草，但這就是我們挑戰自己的程式技巧及邏輯能力的時候了！！
先說明比較簡單的空間複雜度，基本上各種程式語言都有有幾種不同的變數種類，而他們的配置的記憶體大小在不同編譯器上都不相同，以下實際執行程式在不同的電腦及作業系統(C及JAVA比較)：
這些變數型態大小通常以byte為單位，而這樣單看一個變數大小沒有多少，但是當你建立了一個size 為10000 的整數陣列在程式裡面，就相當於是使用了40000bytes，也就是40k。
想想看如果你有一個學生資料結構Student裡面有50個整數變數、50個長度為10的字串，而你又建立了陣列裡面有1000個Student，這個大小是很恐怖的！
而演算法常常會使用到迴圈，所以在寫演算法時要特別注意，有沒有在迴圈內放置建立陣列或是建立物件變數，才不會造成程式無限吃垮電腦的記憶體！所以如果有在刷Leetcode或是準備APCS考試的人可能會看到一些題目會要求使不能另外創建記憶體或陣列來撰寫程式，以降低空間複雜度！
再來就講講時間複雜度，要計算一個演算法的時間複雜度我們就必須推算出演算法執行了多少次的基本運算，基本上我們通常會分別計算最佳情況和最差情況的時間複雜度來作為我們分析演算法的標準
以一個"加總陣列中的項目"來分析：
/// run in java
int arr[] = new int [20];
int sum = 0;
for(i = 0; i < arr.length; i++)
{
sum += arr[i]; ///1 次基本運算 ---- A
}輸入為大小 n = 20 的陣列，需要執行20次((n = 20) * 1)的基本運算，則這個”加總陣列中的項目”演算法的時間複雜度就為O(n)
再舉一個”氣泡排序”演算法來分析：
int arr[] = new int [20];
Random r1 = new Random();
int i = 0;
int j = 0;
int temp = 0;
for(i = 0; i < arr.length; i++)
{
arr[i] = r1.nextInt(100); ///1 次基本運算 ---- A
}for(i = 0; i < arr.length; i++)
{
for(j = 0; j < arr.length - 1; j++)
{
if(arr[j] < arr[j + 1])
{
temp = arr[j]; ///1 次基本運算 ---- B
arr[j] = arr[j + 1]; ///1 次基本運算 ---- C
arr[j + 1] = temp; ///1 次基本運算 ---- D
}
}
}for(i = 0; i < arr.length; i++)
{
System.out.println(arr[i]); ///1 次基本運算 ---- E
}
氣泡排序法中，有兩個單迴圈、一個巢狀迴圈、五個基本運算和一個判斷式，有些書會將判斷式也當作一個基本運算，但在本文章我們不列入計算，之後會發現其實迴圈內有幾個基本運算其實不太影響時間複雜度，比較重要的是迴圈執行了幾次：
氣泡排序法時間複雜度計算 (n = 20):
A : n * 1
B,C,D：(3) => 巢狀迴圈 : n * n * 3 = n² * 3 = 3 * n²
E : n * 1
因此輸入為大小 n = 20 的陣列到氣泡排序法，需要執行3n² + 2n次的基本運算，則這個”氣泡排序法”演算法的時間複雜度就為O(n²)
氣泡排序演算法(BubbleSort)示意圖：
以上兩種演算法可以看出差異，在國高中時我們會學到各種方程式，知道他們的上升趨勢都有所差異，可以看下圖A；而圖B顯示n²在輸入n 越大時，會超越過n的曲線，亦即當我們同時有兩個演算法可以達成同一個目標，我們應該要選擇使用時間複雜度為O(n)的演算法來做運算囉！
而圖A中看到一條上升曲線遠超越其他方程式的曲線 — 2^n，這條曲線有個很經典的演算法，那就是鼎鼎大名的”費波那西”序列(Fibonacci Sequence)，以遞迴方式定義的演算法，是學遞迴很好的範例：
int fib(int n)
{
if(n <= 1)
{
return n;
}
else
{
int val = fib(n - 1) + fib(n - 2); ///1 次基本運算
return val;
}
}最先研究此數列的是義大利人費波那西在研究兔子生長數量時用上這數列；
**第一個月有一對兔子
**一對兔子在兩個月後的每個月都生出另外一對兔子
**兔子永遠不會死去
(費波那西演算法歷史來源取自:維基百科費波那西)
費波那西序列(Fibonacci Sequence)示意圖：
大家也可以自己嘗試實做其他時間複雜度的經典演算法來體會一下，像是”矩陣乘法”(時間複雜度為O(n³))、”二元搜尋”(時間複雜度為O(logn), log以2為底)，都是很好的範例，也剛好可以練習一下基礎的演算法！
這次對於演算法的分析就先到這邊，完整介紹每個演算法真的是落落長，介紹不完。每個演算法基本上都可以整理成一篇文章，之後有機會一定會分享給大家！
如果大家有興趣想研究演算法，推薦一本書《演算法 — 使用C++虛擬碼》，是我從大學宿舍搬到研究所再到工作的一本很好用的工具書，也可以說是帶我進入演算法世界的一本中文演算法聖經了！
喜歡我的文章的人也記得幫我按個拍手、分享，覺得很不錯的可以幫我拍個50下！
也要快點追蹤我的 FB粉絲專頁 — 飛比尋常的程式設計世界 ，不會太頻繁出現在你的塗鴉牆騷擾你，好文章生產需要一點時間，有錯誤或想討論的都歡迎留言給我唷！那就下次見拉！
