王者歸來–演算法

備註: 以下程式範例皆有javascript和python兩種語言的範例。

時間複雜度O(念作Big O，畢格歐)

複雜度取法:

省略係數
取最高的指數

範例:

2n²種組合，則記為O(n²)；
以2為底的log時，則省略2直接以log表示，例如二分法搜尋法等等的演算法，即為O(log n)，另外比較常見的也有O(nlog n)；
如果為常數，則直接記為O(1)

常見的幾個複雜度的比較(由最複雜到簡單):
O(n!) > O(n²) > O(nlog n) > O(n) > O(log n) > O(1)

資料結構

陣列Array

python的array相關語法

陣列操作的時間複雜度的比較

查詢: 可以直接透過array[index] 取得值，所以是O(1)
新增: 在某index插入值，必須遍歷該array，是O(n)
刪除: 在某index刪除值，必須遍歷該array，是O(n)


const array = [1, 2, 3] // javascript


list = [1, 2, 3] # python

鏈結(List Node)

重點在於.next連接下一個node，有單向與雙向鏈結表(linked list)，查找某項資料時需遍歷整個linked list資料(O(n))。

一個鏈結有2個部分: 資料區(data)和指向區(next)

查詢: 必須遍歷整個list，一路往下找資料，所以是O(n)
新增: 只要重新指向資料即可，是O(1)
刪除: 一樣也是只要重新指向資料即可，是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

資料插入堆疊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:






































// 以下僅為示意而已，不一定是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}
]

開放定址法

























// 以下僅為示意而已，不一定是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
myDict = {
  'a': 'a',
  'b': 10,
}





// 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的形式











# 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

陣列
優點: 資料相對簡潔。
缺點: 需要計算index以得知node為哪一層的節點，而且可能會有很多"空節點"。
鏈結
優點: 資料比較直覺，跟二元樹的"結構"差不多。不會有多餘的空節點，且可以用遞迴的方式遍歷所有節點，相當方便。
缺點: 非"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]

泡沫
平均: O(n²)
每一次迴圈都會把值兩兩做比較，每一次都會把最大值"像是泡沫一樣"推到array最右邊，所以被稱為"泡沫排序"法，而排序上每次只要n-2, n-3…的次數做排序即可(因為每一次都會把一個最大值排到右邊)。
total = (n-1) + (n-2) + … + 1
雞尾酒
最佳(如果大多排好): O(n)
平均: O(n²)
為泡沫排序的改良，透過往右找最大值和往左找最小值來將搜尋範圍漸漸縮小(將最大和最小的設為基準點)，如果資料為大多排好的情況，則只要往左和往右找幾次就能排好了。
選擇
平均: O(n²)
依序將最小值往array的最前面放。從index為0開始，找"index~最後"之中的哪個值為最小，與前面的值互換，接著index + 1，重複以上步驟，最後把值從小排到大。
插入
平均: O(n²)
分為往後和往前遍歷，往後的index逐漸增加，而往前則是在"index~0"之中，"前面"的值如果比較大，就跟現在的值對調。這個方法跟"選擇排序"幾乎是相反的，是把比較大往後互換，最後把值從小排到大。
堆積樹
平均: O(nlogn)
堆積樹的根節點必為最小(或最大)值，因此只要持續將值從堆積樹pop(取根節點並排序堆積樹)出來即可。
快速(Quick Sort)
最佳/平均:O(nlogn)
首先隨機挑一個基準值(pivot)，將陣列中的值做比較，如果比基準值還小，則被歸在左半邊，否則就是右半邊。用"遞迴"的方式，再將左半和右半做同一件事，最後將所有值合併在一起，就是小到大的排序了。
合併
平均: O(nlogn)
與"快速排序"法有異曲同工之妙，也是將陣列切開。不過合併排序是從中間切開，將切開後的左半和右半在"合併時"做比較，並且合併為排序好的陣列。如此反覆用"遞迴"的方式，將陣列切到最小，再將每個左半和右半作合併，直到所有都合併完之後，就是已經排序好的陣列了。

程式實例:

https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter9_sort

搜尋法

數據搜尋

找尋陣列中的相符的數值，此書介紹了幾個方法。

順序搜尋法 O(n)
從0開始，依序往1, 2,…n找相符的值，雖然可能很快就找到我們要的值，不過複雜度平均為O(n)









arr = [1, 2, 3, 5, 6]

def find(source, target):
  for data in range(arr):
    if data == source:
      return data
  return None

二分搜尋法 O(logn)
首先此陣列要先"排序"，接著不停地找中位數，比較我要找的值比中位數更大或更小，接著不停地比對該值，直到找到該數值為止。
最大/最小搜尋法 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位元的雜湊值，即便資訊之間只差一個字，輸出的雜湊值也是完全不相同，目前還沒被破解。

金鑰密碼系統

對稱: 加密和解密用的是同一個金鑰演算法
最大缺點為，在傳送金鑰時可能被他人竊取，這個傳送金鑰的困難，又稱為"金鑰傳送困難"。
非對稱: 加密和解密用的是不同的金鑰演算法
金鑰種類:

公開金鑰: 給傳送方的金鑰，常見的為RSA演算法加密金鑰
私密金鑰: 接收方自己的金鑰，不傳給他人

主要運作原理:
接受方擁有公開和私密的金鑰。要傳送資料前，將公開金鑰傳給傳送方，傳送方將資料加密之後傳給接受方，再用私密的金鑰來解密。
可能的威脅: 中間人攻擊

簡單來說，就是駭客用自己的公開金鑰(姑且稱為C)和私密金鑰(C')給傳送方，並從中"攔截"接收方給傳送方的公開金鑰(A)，並將原本的A掉包為C，傳送方因為不知道(沒憑證的情況下)是誰給的，所以用C將自己的資料加密。

接著駭客(現在手中有C, C', A這些金鑰)從中攔截加密後的資料，將其用C'解密為原始資料，再用A這個原本的公開金鑰加密資料，將其傳給接收方，接收方用他的私密金鑰一樣可以解密，接收方沒發現問題，因此也不知道資料已經被攔截"偷看過"了。

要解決這個威脅，可以用SSL協定等等的數位憑證，來將金鑰賦予認證，如此一來可以知道是誰發的金鑰，以減少上述的威脅。

認證與憑證

在原始文件加密後，再用特定算法附上一段HASH雜湊"鑑別碼"(MAC)，成為一個有鑑別碼的加密文件。接收方收到後算出MAC，再和接收方自己算的MAC做比對，如果一致則代表沒被竄改過。

數位簽章

特色為「私鑰加密」、「公鑰解密」，與上述的"中間人攻擊"案例的運作原理剛好相反。
傳送方先在資料中附上數位簽章，接著用私鑰加密。接著傳送公鑰給接收方，再將含有簽章的被加密資料傳給接收方，用該公鑰解密，看是否簽章是否正確，來驗證對方的身分。

數位憑證

https憑證就是使用這個方法。特色為需要先向「認證機構(CA)」申請憑證，你必須提供你的個人訊息(例如姓名、組織等等)和公開金鑰給該機構，接著該機構會將你所有的訊息+公開金鑰用該機構的"私密金鑰"加密，做成一個含有該機構數位簽章的"數位憑證"，將其發送給你，這就是你/你的服務在網路上的"身分證"。

傳送方傳送"數位憑證"給對方，而接收方拿到該數位憑證之後，接著向CA查證之後，再用CA的公開金鑰解密，取得傳送方的公開金鑰，接著就可以相對安全地信任作資料的傳輸了。

相關文章: https://progressbar.tw/posts/98

人工智慧(深度學習)相關演算法–KNN演算法

重點在於"算出特徵數值"，主要用到了"迴歸"與"統計"，算出平均值和近似值。

計算特徵

常用於推薦的演算法，算法是與每個特徵值的距離來看，越近表示越相似則越推薦。公式為畢氏定理的算法，例如，有兩項特徵值分別為a, b，則((a2 - a1)² + (b2 - b1)²)^1/2，算出與目標最相近的。

分群算法

將一堆點做分群，用的是計算特徵的算法做延伸。一開始先設定好分N群，並"隨機挑選"群集的中心點，接著計算"群集中每個點到中心點"最短距離，"重新計算"該中心點的新位置來做"重新分群"，直到每個群集的每個點已經不再變化，表示最佳的分群已經完成。
image alt

程式實例:

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

王者歸來–演算法

時間複雜度O(念作Big O，畢格歐)

資料結構

陣列Array

鏈結(List Node)

一個鏈結有2個部分: 資料區(data)和指向區(next)

程式實例:

佇列Queue

程式實例:

堆疊Stack

程式實例:

2. 雜湊表HashTable

搜尋值時

hashtable實際應用

二元樹相關

二元樹(btree)

基本觀念:

實例如下:

建立二元樹

搜索

新增

刪除

儲存方式

程式實例:

二元搜索法

堆積樹(Heap Tree)

程式實例:

7種排序法

程式實例:

搜尋法

數據搜尋

程式實例:

走迷宮

程式實例:

遞迴

河內塔

八皇后

碎形

程式實例:

圖論(Graph)

各種圖形

廣度優先搜尋

深度優先搜尋

最短路徑算法

程式實例:

貪婪演算法

程式實例:

另外解法–動態規劃

程式實例:

資料加密與資安

各種專有名詞

加密

雜湊(Hash)和SHA

SHA(Secure Hash Algorithm)

金鑰密碼系統

認證與憑證

人工智慧(深度學習)相關演算法–KNN演算法

計算特徵

分群算法

程式實例:

面試常見演算法考題

程式實例:

Read more

【創業】【行銷】興趣的八維度變現思維

怦然心動的工作整理術

文章相關整理與脈絡

UI/UX經驗