還記得在我們程式碼重構的第一天，把難用的資料形狀，改成了比較好處理的資料形狀嗎？

//// 不好用的資料形狀
var itemPrice = [
  {name: "遙控車", price: 250}, 
  {name: "玩偶", price: 180}, 
  {name: "拼圖", price: 120}
];  // 商品價格

var amounts = [2, 0, -10]; // 購買數量

// 不好用的計算方法
itemPrice[0].price * amounts[0]

//===========================================

//// 新的資料形狀

// 商品價格字典, 以後可以很方便的新增或修改商品跟價格
let itemPrice = {
    "遙控車": 250,
    "玩偶": 180,
    "拼圖": 120
}

// 改成用物件，可以用 name 當 key 來取得 itemPrice 的價格
let cart = [
    {name: "遙控車", amount: 2}, 
    {name: "玩偶", amount: 0}, 
    {name: "拼圖", amount: -10}
]

// 好用的計算方法
let {name, amount} = cart[0]
itemPrice[name] * amount

這種知道用哪種資料的形狀，可以讓我們的程式更容易處理的知識，叫做資料結構與演算法 (data structures and algorithms)。這個在程式的領域是很重要的進階級學問，是在大學裡做為一個單獨的課來學習的。

這個領域在討論有什麼程式的流程跟資料的形狀，可以更容易更快的解決問題。

翻字典的方法

資料結構與演算法有一個很經典的問題，就是「怎麼查字典最快？」。例如我們手上有一本 1024 頁的字典，裡面是用每個字的筆劃數排好順序的，而且沒有目錄，那麼當我們想要查任何一個字，你會怎麼翻字典呢？

如果你是每次都從前面開始翻，在遇到筆劃最多的字時，最多要翻到第 1024 次才找得到。反之從後面開始翻，在遇到筆劃最少的字時，最多也是翻 1024 次。

「演算法」會教我們有個很棒的方法：

1. 先翻開正中間那一頁，也就是第 512 頁。
2. 看看這頁第一個字的筆劃，比我們要查的字筆劃多還是少。
3. 如果是我們的字筆劃比較少時，直接去翻前面那半的正中間那頁，也就是第 256 頁。
   如果比較多，那翻後面那半的正中間那頁，也就是第 768 頁。
4. 比較第 256 頁第一個的筆劃，比我們要查的字筆劃多還是少。
5. 如果還是比較少，那就再翻前面那一半，也就是第 128 頁。
   如果比較多，改翻後面那半: 128 跟 256 的中間，也就是第 384 頁。
6. 重複這個動作直到找到。

這個演算法有個名字，叫二分搜尋法。就是每次都可以排除掉一半的意思。

由於每一次翻頁，都可以排除一半無關的資訊，所以一本 1024 頁的字典，不管什麼字，最多就是翻 10 次可以找得到。

而如果變成兩倍厚的字典，2048 頁的話，最多翻 11 次就能找到。

演算法挑戰

每年 12 月 1 日的時候，有個叫 Advent of Code 的網站，會連出 25 天的演算法挑戰，直到耶誕節那天。有興趣的話可以玩玩看。

另外如果你有聽到找工作的人說了刷題，是指去練習在 LeetCode 演算法題庫上的題目。有些大公司會從這裡出面試的題目。如果是想學習的話， exercism、HakerRank 也是不錯的選擇。

跟 AI 聊聊看

如果你不知道你想做的功能會不會太複雜，可以跟 AI 用這幾句話來聊聊看：

• 我想做的這個功能，有沒有什麼效能上的瓶頸
• 這個瓶頸是否能用什麼演算法改進它?

[進階] 在你往下看之前

資料結構及演算法這張地圖是程式領域裡比較進階的知識(當然它也很有趣)，通常只會在你想要寫出相當複雜的功能，或是你的程式要處理的資訊非常多的時候比較用得到。所以不需要急著往下看，而是知道有這個領域，有需要的時候再回來看就可以了。

為什麼 10 次一定翻得完？

把一個數字不斷的除以 2，除幾次會變成 1的概念，在以後學到複雜一點的數學時，會知道可以用次方的概念來計算。

或是次方的逆運算 log

所以當字典變成兩倍厚，也就是 2048 頁時，二分搜尋法最多只要 11 次就一定找得到。只多了一次。

這個概念在演算法裡叫時間複雜度 (Time Complexity)，討論一個演算法在資料量不斷的增加時，所花的時間增加的幅度是多少。我們會用一種叫 Big O 的符號來表示怎麼增加， 有下列這些：

時間複雜度列表

更多的資料結構及演算法

除了常用的 陣列[]與字典{}之外，可以用它們組合成很多種叫做 樹(Tree) 及 圖(Graph) 的資料結構，它們在想要做到很複雜的事的時候非常有用。

營火前的回顧

• 資料結構及演算法討論程式流程的好壞
• 通常要寫很複雜的功能，或是資料量很大時才要擔心
• 跟 AI 聊「演算法」或「資料結構」，它蠻厲害的

小測驗

1. 想想二分搜尋法還可以用在生活中什麼事情上？
2. 全班 30 個學生站成一排，你要找出誰最高。用幾句話說明就好，例如：

1. 從第一個學生開始，記住目前看過最高的學生。
2. 接著看下一個學生，如果比目前記住的還高，就更新記錄。
3. 走完全班後，記錄的就是最高的學生。

有更棒的方法嗎？跟 AI 聊聊看！

3. [相當難] 學校裡每個人都有好朋友，隨便挑一個不是你朋友的人，怎麼算出你經過幾個朋友可以選到這個人？

地圖