# 演算法 Algorithm

### 演算法的簡單定義
輸入+演算法=輸出
Input+Algorithm=Output

假設：我今天要在2和3之間得到6，那我就要在2和3之間，加上一個*號，就可以讓算式設計成2*3=6
為了得到另外一個東西，我輸入一個東西，這個這可以就叫做演算法

`假設：我今天要得到一杯蘋果汁，中間可能經過果汁機，或是用手榨，最後得到一杯蘋果汁，那果汁機或用手，這處理的過程就可以稱作為演算法。`

假設：我今天要煮泡麵加一顆蛋，我們輸入水、泡麵、泡麵調味包、一顆蛋，這碗泡麵的演算法可能會類似：

1.滾水
2.泡麵放進滾水中
3.加入調料包
4.打入一顆蛋
5.煮至熟

### 時間複雜度(Time Complexity)：評估演算法好壞的工具
評估演算法好壞的工具，最基本的兩個指標是：
- 這個演算法有多快
- 需要用到的記憶體有多少

### 大O符號
我們通常用大O符號(Big O notation)來記錄時間複雜度的快慢

假設：今天想要看高年級實習生這部電影，那我可以
1. 打Grab到BGC出租片店，來回車程需要20分鐘
2. 從網路上下載，一部片需要花8分鐘
->那我可能會先選擇2的方案

假設：今天想要看高年級實習生、幸福綠皮書、Love Rosie
1. 打Grab到BGC出租片店，來回車程需要20分鐘
2. 從網路上下載，一部片需要花8分鐘，所以三部片共耗時24分鐘

| | 方案1 | 方案2 |
| -------- | -------- | -------- |
| 租1部片| 打Grab20分鐘|網路下載8分鐘|
| 租10部片| 打Grab20分鐘|網路下載80分鐘|
| 租n部片| 打Grab20分鐘|網路下載8Xn分鐘|

1. 去出租店：所要取得的時間不受想看的電影片數而影響。也就是不管輸入多少需求(input)，輸出(output)所需要的時間不會因此增加。
->O(1)
2. 網路下載：所要取得的時間受想看的電影片數而影響。也就是輸入多少需求(input)，輸出(output)所需要的時間會因這個多少，而增加。
->O(n)

大O符號，是用來描述一個演算法在輸入n個東西時，總執行時間和n的關係
實務上，我們只會紀錄最高次方的那一項，並忽略其所有的係數

### 演算法有多快不是以秒衡量，而是以步驟次數

### 常見的六種時間複雜度與演算法
- O(1)：陣列讀取
- O(n)：簡易搜尋
- O(log n)：二分搜尋
- O(n^2)：選擇排序
- O(nlogn)：合併排序
- O(2^n)：費波那契數列

#### O(1)：陣列讀取
- 代表：不管input多少東西，程式都會在同一時間跑完

fruits=[蘋果,芭樂,葡萄,木瓜] ----->陣列
蘋果 ----->元素
0 ----->索引值

fruits=[蘋果,芭樂,葡萄,木瓜]
這時，我們如果想要知道：水果列這個陣列中任何一個編號所對應到的水果，都只需要把這個索值對應的元素一起印出來，就知道對應的水果是什麼了。

n=0;
print(fruits[n]);
>> "蘋果"

陣列讀取時，因為我們已經知道櫃子的索引值，不管放入的n是多少，程式都可以在"一個步驟"就到達n所對應到編號的櫃子，並取出該元素->O(1)

#### O(n)：簡易搜尋
- 代表：input n個東西，程式就會跟著輸入的n等比例的增加
例如：n=3，程式就會在3個步驟完成

以fruits=[蘋果,芭樂,葡萄,木瓜]這個陣列來舉例：
例如我目前都不知道各個櫃子中，放的是什麼水果，如果我要知道哪個是木瓜，最壞的方法：就會是，一個櫃子、一個櫃子開，開到是木瓜的櫃子。

- 通常程式步驟的時間複雜度會是用程式執行會碰到的最壞狀況 (Worst Case) 來表示，詳細例子我們可以在下面看到。

fruits=[蘋果,芭樂,葡萄,木瓜];
for fruit in fruits:
    if(fruit == "木瓜"){
    print("找到木瓜了！");
    break;
}else{
    print("這裡沒有木瓜T_T");    
}

如果木瓜在第0號櫃子，一個步驟就可以找到他，如果在第3號櫃子，四個步驟才可以找到他。
因此Worst Case是我們剛好要花n個步驟才會找到->O(n)

#### O(log n)：二分搜尋
- 代表：input的數量為n時，執行的步驟數是log n
log n=x 意思是 n=2^x (log以2為底)

假設想要在字典中，找到一個單字，這個字開頭為X，我們可以用前面提過的「簡易搜尋」的邏輯，從A開始找找找；但也可以翻到字典後面，從w字母開頭的字，再繼續找。

假設有一長串有大有小排序好的數字們，我們要在其中找一個特定數字，一樣可以從第一個開始往後檢查。
但更聰明的方法是：先檢查最中間的數字，如果中間的數字比我們要找的數字大/小，我們要找的數量就只剩原本的一半

假設我們今天有七個櫃子
number = [3,14,18,24,30,47,51];
今天要找47這個數字

1. 簡易搜尋：
步驟一：打開第一個櫃子，不是
步驟二：打開第二個櫃子，不是
步驟三：打開第三個櫃子，不是
步驟四：打開第四個櫃子，不是
步驟五：打開第五個櫃子，不是
步驟六：打開第六個櫃子，是

要使用六個步驟才找到47

2. 二分搜尋法
第一步驟：打開第四個櫃子，24 ->比47小，那可以往後找
第二步驟：打開第五個櫃子，不是
第三步驟：打開第六櫃子，是

兩個方法的時間複雜度
1. 簡易搜尋：最壞情況需要7個步驟(要找51)
2. 二分搜尋法：

| 要找的數字 | 3 | 14 |18 |24 |30 |47 |51 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 需要步驟數| 3 | 2 | 3 |1 |3 |2 |3 |

有n個櫃子時，二分搜尋法每在進行一個步驟時，就可以扣除掉一半的可能性，每次都能減少一半，因此二分搜尋法最糟最糟也只需要以2為底的log n 個步驟就可以完成

Numbers = [5,17,33,41,55,61,80]
Find = 55
​
索引值
low = 0
high = len(Numbers) - 1
​
while low <= high:
    mid = (low + high) // 2
    if Numbers[mid] > Find:
        high = mid - 1
    elif Numbers[mid] < Find:
        low = mid + 1
    else:
        break
​
print(mid)

#### 選擇排序法(Selection Sort)
- 只要重複執行兩個步驟
1. 找最小值
從「未排序好的數字」中找到最小值
2. 丟到左邊
把最小值丟到「未排序好的數字」的最左邊，把它標示成已排序好

從n個還沒排序好的數字中找到最小值，需要n個步驟
最常見的找最小值的方法：我們先設陣列的第一個數字是「目前的最小值」，然後往後把陣列的數值一個一個讀取

如果讀取的下個數比最小值大，就什麼都不用做
而讀取到的數字比「目前的最小值」小，就把「目前的最小值」換成這個數。
重複這個方法把所有陣列的數都讀過一遍，就能確保目前的最小值為整個數列的最小值。

#### O(n logn)：合併排序(Merge Sort)
- 代表執行時間會隨著以二為底的log n乘上再n成長
- 最常見的例子是合併排序法(Merge Sort)與快速排序法(Quick Sort)

基本的步驟可以分為「拆分」及「合併」：
拆分：步驟數為 n-1
1. 把大陣列切一半，分為兩個小陣列
2. 把切好的兩個小陣列再各自切一半
3. 重複步驟2直到每個小陣列都只剩一個元素
合併：步驟數為 n * log n
1. 排序兩個只剩一個元素的小陣列並合併
2. 把兩邊排序好的小陣列合併並排序成一個陣列
3. 重複步驟2直到所有小陣列合併成一個大陣列

每回合的合併需要花：O(n)
總共需要回合數：O(log n)

合併排序法總共的步驟數為 n-1 + n log n。
時間複雜度，即為 O( n log n)。