# [資演] 0- 資料結構與演算法簡介
###### tags: `資演`

## 什麼是資料結構？
:::info
**資料結構** (data structure) 指的是電腦中**儲存、組織資料**的方式。
:::
在寫程式之前，我們通常要先規劃好所使用的資料要用什麼格式儲存、表示，而使用適合的資料結構可以讓程式跑起來更有效率，也可以使code更容易閱讀、維護。

可以把資料結構想成是裝載資料的**容器**，而在裝不同東西時，我們會選擇使用不同的容器去裝，比如裝咖啡時使用咖啡杯、裝啤酒時會使用啤酒杯等。學習各種不同的資料結構可以幫助我們更容易去選擇在什麼狀況下該使用怎樣的容器來處理資料。

舉例來說，我們現在有5筆整數資料需要儲存，這些資料對應到5名學生的成績，我們可以使用5個變數來儲存這些資料，其中變數名稱就是學生的名字：

alice = 85
bob = 76
chad = 65
dave = 92
eve = 99

但是學生數量一旦多起來，我們就會有非常多的變數，而這不是我們想要的。如果學生們各自對應有他們的座號，我們可以使用一個list來儲存，其中list的長度是班上學生的數量。現在假設班上只有剛剛提到的5個學生：

score = [0] * 5

score[0] = 85
score[1] = 76
...

其中，list的index對應到的就是學生的座號減去1。如果覺得這樣不夠直觀，或是學生沒有對應的座號、人數也不固定的時候，我們可以改用一個dictionary來儲存成績，其中用來存取成績的key是學生的名字：

score = {}

score["alice"] = 85
score["bob"] = 76
...

從以上這個簡單的例子，我們也能夠看出來，就算是解決相同的問題（儲存成績），我們可以根據使用場景選擇不同的資料結構來將程式的效率最佳化、或是方便程式設計師修改、維護程式等，達成不同的目的。

## 什麼是演算法？
:::info
**演算法**是一個被定義好的、電腦可以執行其指示的有限步驟或次序，包含**一系列定義清晰的指令**，並可於**有限的時間及空間**內清楚的表述出來。
:::
演算法通常不依賴於特定的程式語言，它是一套邏輯，因此可以用虛擬碼 (pseudocode) 、流程圖，甚至是自然語言（我們平常說的話）來描述。

當我們遇到一個問題的時候，可以把這個問題想成一個數學問題，然後設計一連串的解題步驟來解決它，這些步驟就是演算法。

例如，我們現在想喝一杯珍珠奶茶，我們要怎麼設計演算法來解決這個問題呢？

第一步：走去飲料店
第二步：點餐
第三步：付錢
第四步：得到一杯珍珠奶茶

你可能會覺得很奇怪，這樣也算是一個演算法嗎？事實上，演算法就是一連串用於解決問題、完成任務的步驟。

那麼，怎樣才能算是一個好的演算法呢？一個好的演算法必須具備以下兩要素：
* 正確性 (correctness)
你今天想喝一杯珍珠奶茶，結果卻買成一杯啤酒，這不是我們要的結果。一個好的演算法必須正確輸出想要的結果。
* 效率 (efficiency)
這涉及到演算法的表現 (performance)。假設在你家旁邊有一間5X嵐，在距離你家10公里外也有一間5X嵐。一個具有效率的演算法會叫你去你家旁邊那間5X嵐購買珍珠奶茶，而不是距離你家10公里外那家。

那為什麼我們要把演算法跟資料結構放在一起呢？
:::danger
「**程式 = 資料結構 + 演算法**」
:::
每種資料結構都有適合存取它的演算法。選擇不同的資料結構，會影響程式實作的方便性以及效率等。正確的資料結構也可以提高程式主要演算法的效率，而有些資料結構更是為了解決特定問題而設計，兩者其實是相輔相成。

## 常見的資料結構
* 陣列 (array)
陣列應該可以說是最常被使用到的一種資料結構。在Python裡面，陣列可以用一個list來表示，例如：

    a = ["apple", "banana", "mango", "strawberry", "grape"]

其中每個元素 (element) 都有一個代表其位置的index。
然而，Python的list跟 C/C++ 的array有本質上的不同。我們先來講講 C/C++ 的array (以下簡稱array)，它有以下特點：
* 只能儲存**相同類型資料**
* 儲存在**連續記憶體空間**
* 必須事先配置固定的記憶體空間，也就是**長度是預先設定好的**
* 刪除或加入新元素需要移動大量資料，相當費時

然而，Python的list (以下簡稱list) 是怎麼運作的？首先，在一個list裡面可以有各種不同類型的資料，甚至是另一個list：

    a = [1, "apple", 5, [2, 3]]

再者，list的記憶體空間也不是連續的，可以參考[這篇文章](https://medium.com/@t0915290092/%E7%94%A8%E8%A8%98%E6%86%B6%E9%AB%94%E7%AE%A1%E7%90%86%E8%AC%9B%E8%A7%A3%E7%82%BA%E4%BD%95-python-%E7%9A%84-list-%E9%82%A3%E9%BA%BC%E6%85%A2-bf2cd80bbf72)。事實上，要達成和array類似的效果，使用numpy的array更合適。
* 樹 (tree)

樹是一種具有階層結構的資料結構。之所以被稱為樹，是因為它看起來就上一個上下顛倒的樹，根(root)在上，而葉子(leaf)朝下。
* 圖 (graph)

一個圖包含有限個節點(vertex)以及一個無序對（對應無向圖）或有序對（對應有向圖）的集合作為邊(edge)的集合。圖還可能包含和每條邊相關聯的數值，稱為權重(weight)。

## 常見的演算法
* 遞迴(recursive)演算法
:::info
遞迴只應天上有，凡人應當用迴圈。
:::
遞迴是指在函式中使用函式自身的方法。遞迴函式必須有終止條件，才能被計算。遞迴可以使得程式變得更加簡潔，但它的概念並不直覺。
* 分而治之(divide and conquer)
分而治之，指的是將一個大的問題(原問題)分成比較小的部分(子問題)，並且遞迴地解決它們，最後再將這些結果結合起來，得到原先問題的答案。
* 動態規劃(dynamic programming)
當遞迴分割出來的問題，一而再、再而三出現，我們就可以運用記憶法(memoization)儲存這些問題的答案，避免重複求解，以空間換取時間。通常會使用動態規劃的問題會牽涉到**最佳化**，使用動態規劃為的是找出最好的解。
* 貪心(greedy)演算法
貪心演算法指的是一種在每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇，從而希望導致結果是最好或最佳的演算法。

## 小結
以上只是大略的介紹整個資料結構和演算法的藍圖。未來我們會介紹各種資料結構以及演算法的細節，並使用Python實作。