備註: 以下程式範例皆有javascript和python兩種語言的範例。
複雜度取法:
範例:
常見的幾個複雜度的比較(由最複雜到簡單):
O(n!) > O(n2) > O(nlog n) > O(n) > O(log n) > O(1)
python的array相關語法
陣列操作的時間複雜度的比較
const array = [1, 2, 3] // javascript
list = [1, 2, 3] # python
重點在於.next連接下一個node,有單向與雙向鏈結表(linked list),查找某項資料時需遍歷整個linked list資料(O(n))。
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter3-linked-node
重點為 頭進尾出(先進先出)
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter4-queue
重點為 頭進頭出(後進先出)
遞迴的函示就是用stack的方式堆疊在記憶體中,取得最後一個值,可以實際運行factorial這個範例: ch_5_5_factorial.py
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter5-stack
就是鍵值對照表,js或其他語言中為object,python中為dict
每個key值會被"雜湊函數"計算成一個"雜湊值",然後將此雜湊值除以某個數字,所得的"餘數"作為陣列的index,將value存於陣列。
但是一定會有index值重複的情況,此時有2種做法:
// 以下僅為示意而已,不一定是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}
範例:
# python
myDict = {
'a': 'a',
'b': 10,
}
// js
const obj = {
a: 'a',
b: 10,
}
最上方的節點,為根節點(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
也是一種二元樹,但是跟上面提到的二元樹不同,當插入新節點時,會從左到右把空節點依序補齊,因此不太會有一般二元樹只偏頗某一邊的情況發生。
插入節點之後,將節點與父節點比較(看是最小還是最大堆積樹)並對調,如果是最小堆積樹,比父節點小的話,就跟父節點對調,反之亦然。
可應用於排序上(從大到小或從小到大),詳見下個章節的介紹與範例。
堆積樹種類:
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter7_heap
預設都是最小在陣列的最前面[0]
泡沫
平均: O(n2)
每一次迴圈都會把值兩兩做比較,每一次都會把最大值"像是泡沫一樣"推到array最右邊,所以被稱為"泡沫排序"法,而排序上每次只要n-2, n-3…的次數做排序即可(因為每一次都會把一個最大值排到右邊)。
total = (n-1) + (n-2) + … + 1
雞尾酒
最佳(如果大多排好): O(n)
平均: O(n2)
為泡沫排序的改良,透過往右找最大值和往左找最小值來將搜尋範圍漸漸縮小(將最大和最小的設為基準點),如果資料為大多排好的情況,則只要往左和往右找幾次就能排好了。
選擇
平均: O(n2)
依序將最小值往array的最前面放。從index為0開始,找"index~最後"之中的哪個值為最小,與前面的值互換,接著index + 1,重複以上步驟,最後把值從小排到大。
插入
平均: O(n2)
分為往後和往前遍歷,往後的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
找尋陣列中的相符的數值,此書介紹了幾個方法。
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
主要方法為"標記",總共有幾個標記種類:
將走過的路堆疊為stack(array),從起點開始,下一格如果不是死路,則標記"下一格"為通道。
但如果下一格無路可走,則代表"此格"為死路,將其標記為死路,並且"倒退"一格(捨棄剛剛走過的路),重複此行為直到找到出口。
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter11_maze
有三個柱子可以擺放中空盤,分別為來源、輔助和目的。我們的任務是要從來源柱子上,從上到下由小到大擺放的中空盤子,全部都移到目的柱。而盤子不能隨意擺放,無論在哪一個柱子,都必須小的在上,大的在下。
解法為: 不管有幾個盤子,每次就是將來源移到輔助,輔助移到目標,如此反覆循環,用遞迴的方式解決此問題。
圖形的子單元跟主單元長得一模一樣,用遞迴的方式繪製子單元。常見的像是"遞迴樹",雪花等等。
(這部分因為沒有安裝套件,故暫無範例)
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter12_recursive
二元樹也是一種圖形
圖形(每個節點之間有數值,計算點到點之間的最短路徑,例如計算下圖的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為雜湊函數,可以將不同長度的資料轉換為"固定長度"的"雜湊值",雜湊值有128, 256位元等等不同的位元長度。
是目前常用的Hash演算法之一,例如常聽到的Hash-256就是,可以將任何大小的資訊轉為256位元的雜湊值,即便資訊之間只差一個字,輸出的雜湊值也是完全不相同,目前還沒被破解。
主要運作原理:
接受方擁有公開和私密的金鑰。要傳送資料前,將公開金鑰傳給傳送方,傳送方將資料加密之後傳給接受方,再用私密的金鑰來解密。
可能的威脅: 中間人攻擊
簡單來說,就是駭客用自己的公開金鑰(姑且稱為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
重點在於"算出特徵數值",主要用到了"迴歸"與"統計",算出平均值和近似值。
常用於推薦的演算法,算法是與每個特徵值的距離來看,越近表示越相似則越推薦。公式為畢氏定理的算法,例如,有兩項特徵值分別為a, b,則((a2 - a1)2 + (b2 - b1)2)1/2,算出與目標最相近的。
將一堆點做分群,用的是計算特徵的算法做延伸。一開始先設定好分N群,並"隨機挑選"群集的中心點,接著計算"群集中每個點到中心點"最短距離,"重新計算"該中心點的新位置來做"重新分群",直到每個群集的每個點已經不再變化,表示最佳的分群已經完成。
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter18_knn
https://github.com/ms0223900/algorithm-python-and-js/tree/master/practices/chapter19_interviews