# 王者歸來--演算法
備註: 以下程式範例皆有javascript和python兩種語言的範例。
## 時間複雜度O(念作Big O，畢格歐)
複雜度取法:
1. 省略係數
2. 取最高的指數
範例:
* 2n^2^種組合，則記為O(n^2^)；
* 以2為底的log時，則省略2直接以log表示，例如二分法搜尋法等等的演算法，即為O(log n)，另外比較常見的也有O(nlog n)；
* 如果為常數，則直接記為O(1)
常見的幾個複雜度的比較(由最複雜到簡單):
O(n!) > O(n^2^) > O(nlog n) > O(n) > O(log n) > O(1)
## 資料結構
### 陣列Array
python的array相關語法
陣列操作的時間複雜度的比較
1. 查詢: 可以直接透過array[index] 取得值，所以是O(1)
2. 新增: 在某index插入值，必須遍歷該array，是O(n)
3. 刪除: 在某index刪除值，必須遍歷該array，是O(n)
```typescript=
const array = [1, 2, 3] // javascript
```
```python=
list = [1, 2, 3] # python
```
### 鏈結(List Node)
重點在於.next連接下一個node，有單向與雙向鏈結表(linked list)，查找某項資料時需遍歷整個linked list資料(O(n))。
#### 一個鏈結有2個部分: 資料區(data)和指向區(next)
1. 查詢: 必須遍歷整個list，一路往下找資料，所以是O(n)
2. 新增: 只要重新指向資料即可，是O(1)
3. 刪除: 一樣也是只要重新指向資料即可，是O(1)
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter3-linked-node
### 佇列Queue
重點為 ==頭進尾出(先進先出)==
* 新資料插入佇列enqueue: 0 --> [1 | 2 | 3] => [0 | 1 | 2 | 3]
* 讀取佇列dequeue: [0 | 1 | 2 | 3] =讀取=> return 3, [0 | 1 | 2]
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter4-queue
### 堆疊Stack
重點為 ==頭進頭出(後進先出)==
遞迴的函示就是用stack的方式堆疊在記憶體中，取得最後一個值，可以實際運行factorial這個範例: [ch_5_5_factorial.py](https://github.com/ms0223900/algorithm-python-and-js/blob/master/practices/chapter5-stack/ch_5_5_factorial.py)
* 資料插入堆疊stack_push: 0 --> [1 | 2 | 3] => [1 | 2 | 3 | 0]
* 讀取堆疊stack_pop: [1 | 2 | 3 | 0] =讀取=> return 0, [1 | 2 | 3]
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter5-stack
---
### 2. 雜湊表HashTable
就是鍵值對照表，js或其他語言中為object，python中為dict
每個key值會被"雜湊函數"計算成一個"雜湊值"，然後將此雜湊值除以某個數字，所得的"餘數"作為陣列的index，將value存於陣列。
但是一定會有index值重複的情況，此時有2種做法:
* 用鏈結(Linked list)方式串聯value:
```typescript=
// 以下僅為示意而已，不一定是hashtable真正的運作方式
key = sunday
value = 0
key算出來的雜湊值為 12345(假定而已)
12345 % 4 = 1, index 則為1
將value放進array
雜湊array = [empty, {'sunday': 0}]
---
另一個key, value
key = monday
value = 1
key算出來的雜湊值為 12348(假定而已)
12348 % 4 = 0, index 則為0
將value放進array
雜湊array = [{'monday': 1}, {'sunday': 0}]
---
再一個key, value
key = tuesday
value = 2
key算出來的雜湊值為 12362(假定而已)
12362 % 4 = 0, index 則為0
array[0]有值了，所以有衝突! 就不能直接將value放進array!
則用鏈結方式.next串聯值
用()代表串聯值
雜湊array = [
{'monday': 1}({'tuesday': 2}),
{'sunday': 0}
]
```
* 開放定址法
```typescript=
// 以下僅為示意而已，不一定是hashtable真正的運作方式
已經存放值的array
[
{'tuesday': 'T'}.
{'sunday': 'S'},
{'monday': 'M'},
empty,
{'wednesday': 'S'}
]
key = thursday
value = 'T'
key算出來的雜湊值為 12380(假定而已)
12380 % 4 = 0, index 則為0
但是index為0的地方已經被占據，則從0的地方往下找array「空的」地方，找到後塞進array，若是往最後找都找不到時，則從頭開始找。
雜湊array =
[
{'tuesday': 'T'}.
{'sunday': 'S'},
{'monday': 'M'},
{'thursday': 'T'}, // 最後塞在這
{'wednesday': 'S'}
]
```
#### 搜尋值時
用以上的範例來做搜尋
當要找key為'tuesday'時，則用同樣的雜湊函數取得對應的index值，結果為0
搜尋值時，則是array[0].key != 'tuesday' // 不合需求
繼續往下找，array[0].next.key == 'tuesday' // 找到了
找出 {'tuesday': 2}
#### hashtable實際應用
範例:
```python=
# python
myDict = {
'a': 'a',
'b': 10,
}
```
```typescript=
// js
const obj = {
a: 'a',
b: 10,
}
```
---
## 二元樹相關
### 二元樹(btree)
#### 基本觀念:
最上方的節點，為根節點(root node)；
每個節點都可以有"最多2個"子節點(child node)，分別為.left和.right，代表左節點和右節點；
沒有子節點的節點為"葉節點"(leaf node)；
#### 實例如下:
https://codesandbox.io/s/alogorithm-render-xkufd
#### 建立二元樹
==每次都要跟節點比較，比該節點"大"的往右送；比該節點"小"的往左送==
#### 搜索
跟建立的做法差不多，與節點做比較，要搜索的值比現在的節點還大，則往右邊的子節點找，否則往左找。
#### 新增
將新的節點遍歷與比較所有節點，如果比較大則往右，否則往左。
#### 刪除
刪除相對麻煩，除了遍歷並比對數值的相等，還需要補上"空節點"。
#### 儲存方式
可以寫為array(list)或是object的形式
```python=
# list陣列
btree = [10, 5, 20, 3, None, 11, 21] # 沒有按照
# [root, 第一層, 第一層, 第二層, 第二層, 第二層, 第二層]
# listNode鏈結
class Node():
def __init__(self, data=None):
self.data = data
self.left = None
self.right = None
```
1. 陣列
優點: 資料相對簡潔。
缺點: 需要計算index以得知node為哪一層的節點，而且可能會有很多"空節點"。
2. 鏈結
優點: 資料比較直覺，跟二元樹的"結構"差不多。不會有多餘的空節點，且可以用遞迴的方式遍歷所有節點，相當方便。
缺點: 非"plain object"，必須經過處理(inorder print等等)才能其中的資料。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter6-binary-tree
---
### 二元搜索法
<!-- 紅黑二元樹? -->
### 堆積樹(Heap Tree)
也是一種二元樹，但是跟上面提到的二元樹不同，當插入新節點時，會從左到右把空節點依序補齊，因此不太會有一般二元樹只偏頗某一邊的情況發生。
插入節點之後，將節點與父節點比較(看是最小還是最大堆積樹)並對調，如果是最小堆積樹，比父節點小的話，就跟父節點對調，反之亦然。
可應用於排序上(從大到小或從小到大)，詳見下個章節的介紹與範例。
堆積樹種類:
* 最小堆積樹(最小的為根節點)
* 最大堆積樹(最大的為根節點)
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter7_heap
---
## 7種排序法
預設都是最小在陣列的最前面[0]
1. 泡沫
平均: O(n^2^)
每一次迴圈都會把值兩兩做比較，每一次都會把最大值"像是泡沫一樣"推到array最右邊，所以被稱為"泡沫排序"法，而排序上每次只要n-2, n-3...的次數做排序即可(因為每一次都會把一個最大值排到右邊)。
total = (n-1) + (n-2) + ... + 1
2. 雞尾酒
最佳(如果大多排好): O(n)
平均: O(n^2^)
為泡沫排序的改良，透過往右找最大值和往左找最小值來將搜尋範圍漸漸縮小(將最大和最小的設為基準點)，如果資料為大多排好的情況，則只要往左和往右找幾次就能排好了。
3. 選擇
平均: O(n^2^)
依序將最小值往array的最前面放。從index為0開始，找"index~最後"之中的哪個值為最小，與前面的值互換，接著index + 1，重複以上步驟，最後把值從小排到大。
4. 插入
平均: O(n^2^)
分為往後和往前遍歷，往後的index逐漸增加，而往前則是在"index~0"之中，"前面"的值如果比較大，就跟現在的值對調。這個方法跟"選擇排序"幾乎是相反的，是把比較大往後互換，最後把值從小排到大。
5. 堆積樹
平均: O(nlogn)
堆積樹的根節點必為最小(或最大)值，因此只要持續將值從堆積樹pop(取根節點並排序堆積樹)出來即可。
6. 快速(Quick Sort)
最佳/平均:O(nlogn)
首先隨機挑一個基準值(pivot)，將陣列中的值做比較，如果比基準值還小，則被歸在左半邊，否則就是右半邊。用"遞迴"的方式，再將左半和右半做同一件事，最後將所有值合併在一起，就是小到大的排序了。
7. 合併
平均: O(nlogn)
與"快速排序"法有異曲同工之妙，也是將陣列切開。不過合併排序是從中間切開，將切開後的左半和右半在"合併時"做比較，並且合併為排序好的陣列。如此反覆用"遞迴"的方式，將陣列切到最小，再將每個左半和右半作合併，直到所有都合併完之後，就是已經排序好的陣列了。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter9_sort
---
## 搜尋法
### 數據搜尋
找尋陣列中的相符的數值，此書介紹了幾個方法。
1. 順序搜尋法 O(n)
從0開始，依序往1, 2,...n找相符的值，雖然可能很快就找到我們要的值，不過複雜度平均為O(n)
```python=
arr = [1, 2, 3, 5, 6]
def find(source, target):
for data in range(arr):
if data == source:
return data
return None
```
2. 二分搜尋法 O(logn)
首先此陣列要先"排序"，接著不停地找中位數，比較我要找的值比中位數更大或更小，接著不停地比對該值，直到找到該數值為止。
3. 最大/最小搜尋法 O(n)
找最大值或最小值，最簡單的就是，先設定一個初始值(可以用陣列中的第一個)，接著從頭依序找尋比較大(或比較小)的值，取代該初始值，找完所有的值之後，該初始值就是最大/最小的值了。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter10_search
## 走迷宮
主要方法為"標記"，總共有幾個標記種類:
* 還沒走過(0)
* 已經走過(1)
* 死路(2)
將走過的路堆疊為stack(array)，從起點開始，下一格如果不是死路，則標記"下一格"為通道。
但如果下一格無路可走，則代表"此格"為死路，將其標記為死路，並且"倒退"一格(捨棄剛剛走過的路)，重複此行為直到找到出口。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter11_maze
---
## 遞迴
### 河內塔
有三個柱子可以擺放中空盤，分別為來源、輔助和目的。我們的任務是要從來源柱子上，從上到下由小到大擺放的中空盤子，全部都移到目的柱。而盤子不能隨意擺放，無論在哪一個柱子，都必須小的在上，大的在下。
解法為: 不管有幾個盤子，每次就是將來源移到輔助，輔助移到目標，如此反覆循環，用遞迴的方式解決此問題。
### 八皇后
* 溯回演算法:
這方法比較好懂，簡單來說就是依序找每一行(row)能擺的queen，但如果上一行放的queen讓該行無法擺放時，則"退回"上一行，重新擺放queen，直到八個皇后都被擺放至棋盤。
* 遞迴的方式:
原理為找每一行(row)，依序增加row的值，遞迴式的找下一row可以放的queen，且每一次都會累積(因為是遞迴)下一次的結果，每一row都被互相影響著，如果下一row放的位置無法讓前一行有位置放，則該結果會被取代掉，直到計算出所有能放的queen都擺在棋盤上。
### 碎形
圖形的子單元跟主單元長得一模一樣，用遞迴的方式繪製子單元。常見的像是"遞迴樹"，雪花等等。
(這部分因為沒有安裝套件，故暫無範例)
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter12_recursive
---
## 圖論(Graph)
### 各種圖形
二元樹也是一種圖形
圖形(每個節點之間有數值，計算點到點之間的最短路徑，例如計算下圖的A到G最短路徑)
### 廣度優先搜尋
先找完同一層"所有"子節點，再往更深層找。
### 深度優先搜尋
先找下一層的第一個節點，該節點找完所有子節點後，繼續往該節點"更深層"找，直到沒有子節點，才往另一個去找。
### 最短路徑算法
遍歷圖形(Graph)中的所有節點，從起點開始遍歷所有子節點，並找出最小值總和，直到拜訪過所有的節點。有各種算法，其中Bellman ford算法可以算負權重的圖形。
#### 程式實例:
圖形
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter13_graph
最短路徑
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter14_shortest_path
---
## 貪婪演算法
用來算出"還算滿意"的答案，不一定會是"最好"的答案，會隨著一開始的選擇以及圖形節點順序的不同(權重都一樣)，而產生不同的結果
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter15_greedy
## 另外解法--動態規劃
除了用貪婪演算來算出"還行"的解答，動態規劃可以算出最佳解答，用的就是二維"表格"的方式。
用表格(二維陣列)來填入計算各種可能，重點是將主問題拆解為子問題，看該欄位還可以放哪些選項(物品)，一個欄位不只可以塞一個值，如果還有多餘的"空間"，則看最多還能塞多少，最後看此表格的"最右下角"能夠塞到多少的最大值(價值)。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter16_dynamic_plan
---
## 資料加密與資安
### 各種專有名詞
* 竊聽: 傳送過程(路由器、伺服器等等各種管道)中"竊取"資訊。
* 解決方法: 資料加密
* 竄改: 在傳送過程中掉包真正的數據，接收方拿到"不正確的資料"。
* 解決方法: 數位簽章、訊息識別碼
* 詐騙: 駭客偽裝成接收方
* 解決方法: 數位簽章、訊息識別碼
* 拒絕: 傳送方傳送資訊，但接收方表達"沒收到"，可能造成糾紛。
* 解決方法: 數位簽章
### 加密
將原始資料加工成難以解讀的資料，就稱為「加密」。
而加密資料的演算法則稱為「金鑰」，即便駭客拿到加密後的資料，沒有「金鑰」通常難以讀取原始資料。接收方需要有金鑰才能夠解密並讀取正確的資料。
### 雜湊(Hash)和SHA
Hash為雜湊函數，可以將不同長度的資料轉換為"固定長度"的"雜湊值"，雜湊值有128, 256位元等等不同的位元長度。
#### SHA(Secure Hash Algorithm)
是目前常用的Hash演算法之一，例如常聽到的Hash-256就是，可以將任何大小的資訊轉為256位元的雜湊值，即便資訊之間只差一個字，輸出的雜湊值也是完全不相同，目前還沒被破解。
#### 金鑰密碼系統
1. 對稱: 加密和解密用的是同一個金鑰演算法
最大缺點為，在傳送金鑰時可能被他人竊取，這個傳送金鑰的困難，又稱為"金鑰傳送困難"。
2. 非對稱: 加密和解密用的是不同的金鑰演算法
3. 金鑰種類:
* 公開金鑰: 給傳送方的金鑰，常見的為RSA演算法加密金鑰
* 私密金鑰: 接收方自己的金鑰，不傳給他人
4. 主要運作原理:
接受方擁有公開和私密的金鑰。要傳送資料前，將公開金鑰傳給傳送方，傳送方將資料加密之後傳給接受方，再用私密的金鑰來解密。
5. 可能的威脅: 中間人攻擊
簡單來說，就是駭客用自己的公開金鑰(姑且稱為C)和私密金鑰(C')給傳送方，並從中"攔截"接收方給傳送方的公開金鑰(A)，並將原本的A掉包為C，傳送方因為不知道(沒憑證的情況下)是誰給的，所以用C將自己的資料加密。
接著駭客(現在手中有C, C', A這些金鑰)從中攔截加密後的資料，將其用C'解密為原始資料，再用A這個原本的公開金鑰加密資料，將其傳給接收方，接收方用他的私密金鑰一樣可以解密，接收方沒發現問題，因此也不知道資料已經被攔截"偷看過"了。
要解決這個威脅，可以用SSL協定等等的數位憑證，來將金鑰賦予認證，如此一來可以知道是誰發的金鑰，以減少上述的威脅。
#### 認證與憑證
* MAC
在原始文件加密後，再用特定算法附上一段HASH雜湊"鑑別碼"(MAC)，成為一個有鑑別碼的加密文件。接收方收到後算出MAC，再和接收方自己算的MAC做比對，如果一致則代表沒被竄改過。
* 數位簽章
特色為「私鑰加密」、「公鑰解密」，與上述的"中間人攻擊"案例的運作原理剛好相反。
傳送方 先在資料中附上數位簽章，接著用私鑰加密。接著傳送公鑰給接收方，再將含有簽章的被加密資料傳給接收方，用該公鑰解密，看是否簽章是否正確，來驗證對方的身分。
* 數位憑證
https憑證就是使用這個方法。特色為需要先向「認證機構(CA)」申請憑證，你必須提供你的個人訊息(例如姓名、組織等等)和公開金鑰給該機構，接著該機構會將你所有的訊息+公開金鑰用該機構的"私密金鑰"加密，做成一個含有該機構數位簽章的"數位憑證"，將其發送給你，這就是你/你的服務在網路上的"身分證"。
傳送方傳送"數位憑證"給對方，而接收方拿到該數位憑證之後，接著向CA查證之後，再用CA的公開金鑰解密，取得傳送方的公開金鑰，接著就可以相對安全地信任作資料的傳輸了。
相關文章: https://progressbar.tw/posts/98
---
## 人工智慧(深度學習)相關演算法--KNN演算法
重點在於"算出特徵數值"，主要用到了"迴歸"與"統計"，算出平均值和近似值。
### 計算特徵
常用於推薦的演算法，算法是與每個特徵值的距離來看，越近表示越相似則越推薦。公式為畢氏定理的算法，例如，有兩項特徵值分別為a, b，則((a2 - a1)^2^ + (b2 - b1)^2^)^1/2^，算出與目標最相近的。
### 分群算法
將一堆點做分群，用的是計算特徵的算法做延伸。一開始先設定好分N群，並"隨機挑選"群集的中心點，接著計算"群集中每個點到中心點"最短距離，"重新計算"該中心點的新位置來做"重新分群"，直到每個群集的每個點已經不再變化，表示最佳的分群已經完成。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter18_knn
---
## 面試常見演算法考題
* 質數:
先將原數字開根號並取其最小整數，檢查其因數是否有大於1的因數即可，如果沒有大於1的因數則表示該數字為"質數"。
* 回文:
將字串轉為陣列，從前面和從後面各拿一個字，比對看是否一樣，直到剩下0~1個字。
* 最大公因數:
* 逼近法: 從2開始一個個找是否為兩數的因數，直到該因數等於其中比較小的數字。
* 輾轉相除法(歐幾里得法): 兩數字先比較，除數為比較小的(假如為A)，被除數為比較大的(B)。接著，兩數相除所得的餘數再作為除數，而原本比較小的數字(A)則是作為被除數，如此相除直到"餘數為0"，取最後一個被除數就是兩者的最大公因數。
* 最小公倍數:
為兩數相乘 除以 兩數的最大公因數。
* 雞兔同籠:
可以用數學的二元一次方程式來解，也可以用程式直接一個個逼近來算。
* 挖金礦:
同動態規劃的問題。
#### 程式實例:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter19_interviews
Sign in with Wallet
Connect another wallet