擁抱「資料結構」的「演算法」(18) - 何謂演算法 Algorithm
前言
在程式設計中資料結構與演算法是非常重要的兩大環節，而演算法就是一組用來解決問題的指令，在處理某些問題或情境時，是否能挑選合適的資料結構並搭配快速有效的演算法是工程師需要培養的基礎能力，前半部的文章，讓我們對於資料結構有初步的認識，接下來，後半部的文章會著重在演算法的介紹，就讓我們一起來進入演算法的世界吧
生活常識
你有烹飪的經驗嗎？如果沒有也沒關係，那正好可以去翻閱食譜，如果今天想吃青菜，就可以參閱食譜上的步驟說明
- 買菜、挑菜
- 洗菜、洗鍋子
- 開抽油煙機、開瓦斯
- 熱鍋子、倒油
- 把菜丟進去拌炒
- 調味、盛盤
圖片來源:https://www.pexels.com/zh-tw/photo/3564599/
依照上述步驟就可以完成炒一道菜，所以透過清楚的步驟說明，就可以完成想吃青菜的願望，但有些人可能會有問題，如果不喜歡吃炒的，可以生吃或吃水煮的嗎？當然可以囉！只要可以用青菜填飽你的胃，各式各樣的青菜食譜都是 OK 的，差別在於你今天的需求是什麼，如果今天想吃青菜但是在減肥，或是因為生理因素不能吃過油的食物，也許就沒這麼適合使用炒的方式，可以改吃生菜或燙青菜
根據上述例子，根據情況不同，操作步驟也會不一樣，而這些根據各式各樣不同情況或問題而推出的食譜，我們只要跟著步驟做，就能解決我們各式各樣的飲食需求
還記得前幾天題過的果汁機嗎？將蔬果丟入機器之後，就會變成果汁，其實都是類似的原理，中間都有一道加工處理的手續
專業知識 - 演算法 Algorithm
資料 A 轉換成資料 B 的過程，中間的處理過程就是演算法，演算法是一組用來解決問題的指令，這些指令可以透過我們自行撰寫，清楚的告訴電腦要執行哪些步驟，而這些步驟需要透過我們的整理與分析後，才能告訴電腦要如何處理，除了程式的可執行性之外，如何迅速有效處理好資料，也是演算法中重要的一環
必要因素
- 輸入：最初提供的資料
- 輸出：最後得到的資料
- 明確的指令：明確清楚定義所要執行的動作
- 有限的步驟：步驟有一定的數量，不會永無止盡
- 有效的作法：可驗證資料的正確性，例如可用紙本驗算
表示法
文字
就像食譜的步驟一樣，就文字敘述，但演算法會筆食譜嚴謹很多，一定要把問題的細節處理都寫清楚並將操作步驟說明清楚虛擬碼 Pseudo Code
是一種演算法的描述語言，介於自然語言與程式語言的之間，所以非資訊相關領域的人不太容易看懂，主要是在表達解決問題的邏輯與架構，方便工程師閱讀完成之後，可自行透過程式語言撰寫要執行的程式碼流程圖 Flow Chart
流程圖在生活中蠻常見到的，像是政府機關的申請流程，就蠻常以流程圖顯示，而在演算法中也可以理用此方法來表示處理步驟的流程
效能分析
如何評估一個演算法的效能好不好呢？是程式碼寫得比較少行就比較快嗎？還是管他的，能動就好(被揍)，通常我們會去考量兩個主要因素：
時間複雜度 (Time Complexity)
是主要判斷演算法優劣的主要考量，不管程式碼是寫了多少行，都還是要依照實際的執行時間去評估優劣，並不一定程式碼少就會比較快，主要還是要看資料在演算法是使用哪一種運算方式，又以三種符號來表示時間複雜度：O (Upper Bound)：最壞情況下(Worst Case)，最久需要花多少時間Ω (Loser Bound)：最好情況下(Best Case)，最少需要需要多少時間Θ (精確度高於 O 與 Ω)：平均情況(Average Case)，通常需要需要多少時間，介於 O 與 Ω 之間空間複雜度 (Space Complexity)
執行演算法時所使用的記憶體空間，這邊比較特別的是，有時候我們可以透過使用較多的記憶體空間來降低執行時間，或是使用較少的記憶體空間來增加演算法的執行時間，就像台北到高雄到底要搭火車還是高鐵？如果選擇搭高鐵的人就是用比較貴的車資來換取時間，雖然車資比較貴，但可以比較快抵達目的地，那選擇搭火車的人，雖然車資便宜但相對的花費的時間比較久，所以講回電腦的記憶體，記憶體就是我們的資源，所使用的資源越多，執行時間可能會比較快，但也不能求快就無限度的使用記憶體，程式雖然可以跑很快，但電腦記憶體使用到 100% 時，電腦很可能就當機了
Big O
假設我們想要求兩數 8 與 12 的最大公因數，那我們首先可能要去翻一下學小的數學，複習一下怎麼求最大公因數，了解數學算式之後，我們得知可以使用短除法，或輾轉相除法，甚至是暴力法去推得最大公因數是 4 ，但每一種方法的執行速度有快有慢，而在演算法中，執行時間的上限值(Upper Bound)，用來表示最差情況下的執行時間，也常常是我們比較演算法速度的主要考量，以下以陣列讀取來做說明
- O(1)
執行時間不受輸入的資料量的影響，例如一個長度為 7 陣列，稱為 A，要讀取索引 2 的資料，如果有另外一個陣列長度為 70 ，稱為 B，也要讀取陣列所引 2 的位置，那就是直接存取 A[2] 與 B[2]，就可以拿到資料，並不需要做額外的運算
void Main()
{
var numbers= new int[]{1, 2, 3};
print(numbers);
}
public void print (int[] array) {
Console.WriteLine(array[2]);
}
輸出結果 :
3
- O(n)
輸入的資料變多，輸出的內容也越多時，執行時間會等比例增加，例如要將長度為 3 陣列，稱為 A，要將 3 個索引位置中的資料印出來，而需要印出 3 次，如果有另外一個陣列長度為 70 ，稱為 B，要將 B 的內容全部印出來，則需要 70次
void Main()
{
var numbers= new int[]{1, 2, 3};
print(numbers);
}
public void print (int[] array) {
foreach(var data in array){
Console.WriteLine(data); // 會執行 3 次
}
}
輸出結果 :
1
2
3
- O(
)
輸入的資料變多，執行時間會以指數增加，例如陣列長度為 3，要得到陣列中任兩數相乘的結果，總共要計算 9 (3 的平方)次
void Main()
{
var numbers= new int[]{1, 2, 3};
print(numbers);
}
public void print (int[] array) {
foreach(var a in array){
foreach(var b in array){
Console.WriteLine(a * b); // 會執行9次
}
}
}
輸出結果 :
1
2
3
2
4
6
3
6
9
O(log n)、O(n log n)、 O(n!)
最後常見的的執行時間還有這些，會在後續章節講到相關演算法的時候再說明，會比較清楚執行時間由小至大排序表
| 執行時間 | 說明 |
|---|---|
| O(1) | 常數時間 |
| O(log n) | 對數時間 |
| O(n) | 線性時間 |
| O(n log n) | 線性乘對時間 |
| O( | 平方時間 |
| O(n!) | 階乘時間 |
陣列與連結串列比較圖
| 陣列 | 連結串列 | |
|---|---|---|
| 讀取 | O(1) 可透過索引快速讀取 | O(n) 逐一存取 |
| 新增 | O(n) 需要搬移其他項目 | O(1) 修改指標 |
| 刪除 | O(n) 需要搬移其他項目 | O(1) 修改指標 |
今日小結
演算法三個是看起來很抽象，但其實就是一種解決問題的方法，在解決問題的過程中會培養我們的思維邏輯，與解決問題的能力，在我們日常生活中常常有很多大大小小的事情要處理，其實每個人都有自己的處理方式，甚至很多人出書分享好用的撇步，其實那些都是生活的智慧，告訴我們要遇到某些問題要如何排解，而演算法也是如此的，只是演算法主要是解決電腦科學領域的問題，先了解問題本身在逐步拆解，像是 Facebook 或 Youtube 的推薦演算法一樣，或是模擬動物行為，像是螞蟻演算法，都是是非常靈活的，或許你也有機會創造屬於你自己的演算法，到時候可能要煩惱演算法要取什麼名字XD
今日謎題
地上有一張神秘的英文數字表格圖，請問你能發現其中暗藏的訊息嗎？
昨日解謎
將 ATTITUDE 的每個字母，各別對應到的數字之後，全部加總起來，即可得到 100 ，是不是很神奇呢
留言
張貼留言