# Lecture 1

## Reference

[Lec01 資料結構 第一週課程](https://youtu.be/3503j2L6qNA)

## Notes

### Top-down analysis (01:54)

1. 設計時可以先了解**使用者需求**，由使用者的角度**決定輸入、輸出型態**。
2. 有了宏觀的角度後，再循序漸進從微觀的角度思考**該由甚麼資料型態、演算法**來實現功能。

### Verification (05:06)

- Correctness & Efficiency
- 寫完程式後，需先測試**程式的正確性**，因此需要設計許多測試用**輸入(test pattern)**。
- 除了正確性之外，**時間及空間上的效率取捨**也是一項驗證重點。
- Scalability
- 設計演算法時要考慮到輸入資料的**數量級**會不會對效能產生影響。
- 這會牽涉到**時間/空間複雜度**(time/space complexity)。
- Error removal
- 除了完成功能之外，**錯誤訊息(error message)及使用手冊(documentation)**也是很重要的一環。
- 例如：*”error 404: Not found”*告訴你此網站不存在，這可以讓接手你程式碼的開發者可以**更有效率的debug**。
- Code readable
- 盡量讓程式碼具有可讀性，例如**變數名**稱可以讓它更有意義一點，避免取一些叫做a, b, c, xx, yy這種**看不出來要拿來完成甚麼事情**的變數名稱。

### Data abstraction (17:47)

- Data type: objects & operations
- **物件(objects)**比較像是**儲存資訊的型態**，而**運算(operations)**則說明可以對這些物件做**哪些運算。**
- Abstract Data Type (ADT)
- 只說明這個**資料型態**應該要**記錄哪些資訊**，以及可以做的**運算**，不考慮用程式碼實現的細節，只考慮這個資料型態的**抽象概念**。
- 例子：自然數(正整數)
- 為了記錄這個資料型態，需要的物件及是能夠儲存*0, 1, 2, …*等數字的**物件。**
- 我們可以對這些物件做一些**運算**，比如說判斷這個數字是不是*0、*加減法等等。


### Algorithm (24:37)

- 演算法(algorithm)是指**處理問題的方法**，撰寫程式碼的過程比較像是一個**實現演算法**的過程。
- Pseudo code，有點像是在寫程式碼，不過只寫出每一行你要做的事情是甚麼，語法甚麼的**先寫個大概**就好(可參考selection sort的範例)。
- 選擇排序法 (Selection sort) (27:12)
- 是一種排序演算法。
- 方法顧名思義，做的事情就是**從還沒排序過的數字們中，選出最小或最大值放到最前面**，接下來從剩下的數字中，再做一次一模一樣的事情。
- Pseudo code example:


- Illustration
1. Original: 一開始這六個數字都還沒排序過，這時最小值是*8*，**因此把*8*這個數字所在的位置跟最前面交換(*34*這個數字)**，這樣就完成一次pass了。
2. After pass 0: 現在剩下後五個數字，這時候最小值是*21*，因此這個時候*21*要跟*34*交換位置。
3. After pass 1, 2, 3, 4: 同理，注意這樣其實總共只做了*6-1=5*次交換而已，因為前六個數字排好了，就等於最後一個數字一定是最大的數字。


### Binary Search (38:22)

- 這個演算法要做的事情是**判斷某個數字有沒有存在在一個陣列(array)裡面**，也就是搜尋(search)。
- 先決條件(Prerequisite): **數字要排序過才可以用**。
- 方法有點像是**二分法**，一開始先從陣列的最中間那個值開始判斷，如果那個值不是要找的數字的話，那就看這個數字是比中間值還小/大，那就往這個值的左/右邊去找(這也是為甚麼數字要排序過的原因)，重複做這件事情直到陣列沒辦法再切成一半了。
- Illustration
- 圖片中上半部分
1. 現在要看*6*這個數字有沒有在這個陣列裡面
2. 先跟陣列正中間的數字*14*比較，很明顯*6*跟*14*是不一樣的數字，而且*6*比*14*小，因此接下來要往*14*左邊的所有數字去找。
3. 比*14*還小的數字中，中間值是*6*，剛好是我們要找的數字，因此這個演算法就結束了，回傳*True*之類的值告訴使用者*6*有在這個陣列裡面。
- 圖片中下半部分
1. 現在要看*25*這個數字有沒有在這個陣列裡面
2. 先跟陣列正中間的數字*14*比較，很明顯*25*跟*14*是不一樣的數字，而且*25*比*14*大，因此接下來要往*14*右邊的所有數字去找。
3. 比*14*還大的數字中，中間值是*22*，跟我們要找的數字不一樣，所以繼續往右邊的數字去找。
4. 此時中間值變成*26*，一樣還是沒找到*25*，繼續把陣列切成一半。
5. 現在只剩下*24*這個數字跟*25*比較了，然而還是沒找到*25*，因此這個演算法就結束了，回傳*False*之類的值告訴使用者*25*沒有在這個陣列裡面。


### Selection problem (54:42)

- 從*N*個值中找出第*K*大的數字。


- 方法一：直接把全部*N*個數字做排序，然後看第*K*個位置的值是誰就好。
- 方法二：先把前面*K*個值選出來放到另外一個陣列裡接著做排序，然後從第*K+1*個值開始跟另外一個陣列裡的值做比較，如果比那個陣列裡的某個值大就替換掉那個數字，然後再排序一次。
- 教授的觀點：方法二比較好，因為當*N*很大的時候，方法一要花比較久的時間(對*N*個數字做排序，做一次就好)，方法二則比較少(對*K*個數字做排序，但是排序的次數比較多)。

### Recursive algorithm (01:05:32)

- Direct recursion: 會**呼叫自己**的函式
- Indirect recursion: 會**呼叫別的函式的函式**，而那個**被呼叫的函式又會去呼叫別人**…
- Boundary: 由於這種**遞迴**式的函式會一直呼叫，所以要設一些邊界條件讓他停下來，不然會程式會卡住。
- 例子：階乘
- 假設我們把**計算階乘**當作一個函式：

$$
f(n) = n! = n * (n - 1) * (n - 2) * \cdots * 2 * 1
$$

- 而階乘也可以這樣表示：

$$
n! = n * (n - 1) * (n - 2) * \cdots * 2 * 1 = n * (n - 1)!
$$

- 因此綜合起來可以這樣寫：

$$
f(n) = n! = n * (n - 1)! = n * f(n - 1)
$$

- 此時我們就有了遞迴的形式，因為$f(n)$取決於$f(n-1)$。
- 例子：遞迴乘法
- 假設有一個函式要做乘法：

$$
g(a, b) = ab
$$

- 這也可以展開變成：

$$
ab = a * (b - 1) + a = g(a, b - 1) + a
$$