如果昨天是資料結構，那今天必然是來討論演算法啦！
「演算法」是另一個會讓許多非本科系的 developer 嚇到的詞彙，會覺得好像是很高深難懂的技術，應該都是 Google 等級的程式設計師才會用到吧？
但很神奇的是，明明是看起來這麼難的一個詞彙，反而滿常出現在媒體用語中的：
所以今天讓我們來揭開演算法神秘的面紗吧！
跟昨天一樣，今天主軸在於讓大家初步認識演算法，沒有要帶著大家到處去刷題，如果有興趣想用演算法來實際解題，歡迎到我的隊友系列文，用 LeetCode 刷題來練習！
由有限步驟所構成的集合，可以用於解決某一個特定的問題。
簡單來說，有點像是「解決某個問題的步驟流程」，比如在生活上，我們要做家事洗衣服：
沒錯，上述五個步驟就是為了完成「洗衣服」這個任務，的其中一種演算法！那有沒有其它演算法？
有啊！衣服一定要自己洗嗎？
所以，要完成一件事情，演算法不只一種唷！
這只是個範例，衣服請自己洗嘿！
其實，「如何把大象放進冰箱裡」這個冷笑話，也是演算法的一種哦：
是不是步驟非常明確，而且能夠解決問題呢XD
而在計算機科學的領域，演算法其實也是在做同樣的事情，我們透過設計一連串的指令、動作，讓電腦去執行，以便協助我們解決一些特定問題。
因此，就算是最簡單的：我想條列出商品名稱與對應的價錢，都是演算法的一種哦！
const products = [
{ name: 'TV', price: 12000 },
{ name: 'laptop', price: 25000 },
{ name: 'washing machine', price: 8000 },
];
products.forEach(product => console.log(`${product.name} 的價錢是 ${product.price}`));
執行結果
TV 的價錢是 12000
laptop 的價錢是 25000
washing machine 的價錢是 8000
演算法其實就是「解決問題的方法」，所以這個問題應該改成：
解決問題的方法有好壞之分嗎？
嗯。。。聽起來是有的，只是我們不會說哪個方法絕對好，而是會用兩個指標來衡量：動用的資源以及花費的時間。
而這兩個指標放在計算機科學領域，就是你曾經聽過的：
空間複雜度就是，我用了多少記憶體空間來完成這件事。
比如要把一個陣列的順序完全反轉：
const reverseArr = (input) => {
const output = [];
input.forEach(item => output.unshift(item));
console.log(output);
};
const arr = [1, 2, 3, 4, 5];
reverseArr(arr);
執行結果
[5, 4, 3, 2, 1]
可以看到為了達成「反轉」這件事情，我多宣告了一個 output 陣列(花到額外的空間來放)，裡面總共有五格，所以看起來 reverseArr 的空間複雜度是 5？
感覺怪怪的對吧！因為這個 output 會根據 input 進來的參數大小，而有所不同，因此我們不能夠直接說空間複雜度是 5。
我們使用 Big O notation，表達在「最壞情況下的複雜度等級」，如果像上例複雜度會隨著 input 線性變動的，會用 O(n) 來表示。
那如果不會隨著 input 變動的會像這樣：
const reverseArr = (input) => {
let temp;
const length = input.length;
for(let i = 0; i<=length/2; i++) {
temp = input[i];
input[i] = input[length-i-1];
input[length-i-1] = temp;
}
console.log(input);
};
const arr = [1, 2, 3, 4, 5];
reverseArr(arr);
執行結果
[5, 4, 3, 2, 1]
可以看到上面的寫法，同樣是為了達成「反轉」這件事情，但我都在 input 本體上面操作，完全沒有使用到額外的空間 output，也就是說，無論 input 的 length 有多大，這個函式都不會花費更多空間，稱之為 O(1)。
其中 1 其實是代表常數，並不是真的只花 1 個空間，而是表達不會隨著
input.length變動
上面還有提到另一個重點是，Big O 代表的是「最壞情況」，會這樣說是因為執行一段程式所花費的時間或空間，有可能有三種情況：
比如說，我們要從陣列中找到一個元素，只要找到就可以不用繼續找了：
const findElement = (input, element) => {
const length = input.length;
for(let i = 0; i<length; i++) {
if (input[i] === element) break;
}
};
const arr = [1, 2, 3, 4, 5];
findElement(arr, 3);
像上面這種程式，執行 findElement(arr, 3) 只要跑三次迴圈就結束了，但如果執行 findElement(arr, 5) 就要跑五次迴圈(雖然這個範例的空間複雜度都是一樣的)。
因此我們會有上述三種情況，但計算機科學領域特別重視「上限」，才能夠確保系統能夠負荷最嚴重的狀況，所以我們才會只強調「最壞狀況」。
時間複雜度則是，我花了多少時間來完成這件事。
但這邊有一點要特別注意，並不是單純指花了幾分鐘來執行，因為每台電腦效能不一樣，我們不是要衡量哪一台電腦比較快，而是「不同的程式寫法在同一台電腦上執行」時的複雜度，因此我們會使用「執行了多少指令」來計算複雜度。
以剛剛上面的例子：
const reverseArr = (input) => {
const output = []; // 1
input.forEach(item => output.unshift(item)); // n
console.log(output); // 1
};
const arr = [1, 2, 3, 4, 5];
reverseArr(arr);
可以看到我在註解的地方寫上了複雜度等級，總共合起來是 n+2，我們只取次方最高的 n，因為當 input 增加時，變化最大的會是最高次方的 n，所以 reverseArr 的時間複雜度就是 O(n)。
可以看到剛剛同樣是一個「反轉」的任務：
output
這代表時間與空間這兩種「效能」是 trade-off，很多時候如果要空間就得花時間，要時間就要花空間。
簡直跟租房子一樣，要大套房就要增加通勤時間
而這大多時候沒有正確答案，只取決於當下的需求，看是犧牲哪一邊比較恰當。(當然如果資料量根本不大，基本上電腦也不痛不癢)
這個網站很視覺化呈現了，不同複雜度執行起來的差異：
演算法也是大學資工系基礎必修的一環，而且通常會跟資料結構相互配合，畢竟，使用怎樣的資料結構，會直接影響到演算法的複雜度，因此資料結構+演算法一起學，報個 2 次鐵人賽 60 天應該就可以了XD"
大多數人會覺得演算法很高深莫測，都是高手在用的，但其實經過今天的說明，不難看出其實，1+1 也是相加的一種演算法，演算法就只是達成目標所需的步驟而已。
之所以會看起來高大上，是因為如最後所說的，只有輸入資料量龐大的時候，才容易看出演算法好壞的落差，而會碰到龐大輸入量的，當然都是高手啦！
所以希望大家不要被「演算法」這個名字嚇到，去了解它，並且試著思考自己的程式是否有更好的演算法，即便資料量不大，也能夠在思考的過程中成長！
荊棘的路險峻
遠繞的路疲倦
在不知道是否存在的交會點
尋一處沙洲
iThome鐵人賽
看影片追技術