---
# System prepended metadata

title: Lecture 1

---

# 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、*加減法等等。

![Untitled](Lecture%201%202422ff366f2248f4a4fb87d2f01b595b/Untitled.png)

### Algorithm (24:37)

- 演算法(algorithm)是指**處理問題的方法**，撰寫程式碼的過程比較像是一個**實現演算法**的過程。
- Pseudo code，有點像是在寫程式碼，不過只寫出每一行你要做的事情是甚麼，語法甚麼的**先寫個大概**就好(可參考selection sort的範例)。
- 選擇排序法 (Selection sort) (27:12)
    - 是一種排序演算法。
    - 方法顧名思義，做的事情就是**從還沒排序過的數字們中，選出最小或最大值放到最前面**，接下來從剩下的數字中，再做一次一模一樣的事情。
    - Pseudo code example:
    
    ![](https://i.imgur.com/FaaUbke.png)
    
    - Illustration
        1. Original: 一開始這六個數字都還沒排序過，這時最小值是*8*，**因此把*8*這個數字所在的位置跟最前面交換(*34*這個數字)**，這樣就完成一次pass了。
        2. After pass 0: 現在剩下後五個數字，這時候最小值是*21*，因此這個時候*21*要跟*34*交換位置。
        3. After pass 1, 2, 3, 4: 同理，注意這樣其實總共只做了*6-1=5*次交換而已，因為前六個數字排好了，就等於最後一個數字一定是最大的數字。
    
    ![](https://i.imgur.com/3jgNJFx.png)


### 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*沒有在這個陣列裡面。

![](https://i.imgur.com/EXUFnoU.png)


### Selection problem (54:42)

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

![](https://i.imgur.com/73Z1wDL.png)

- 方法一：直接把全部*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
    $$