Try   HackMD

王者歸來演算法

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

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

複雜度取法:

  1. 省略係數
  2. 取最高的指數

範例:

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

常見的幾個複雜度的比較(由最複雜到簡單):
O(n!) > O(n2) > 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)
const array = [1, 2, 3] // javascript
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

  • 資料插入堆疊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
  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(n2)
    每一次迴圈都會把值兩兩做比較,每一次都會把最大值"像是泡沫一樣"推到array最右邊,所以被稱為"泡沫排序"法,而排序上每次只要n-2, n-3的次數做排序即可(因為每一次都會把一個最大值排到右邊)。
    total = (n-1) + (n-2) + + 1

  2. 雞尾酒
    最佳(如果大多排好): O(n)
    平均: O(n2)
    為泡沫排序的改良,透過往右找最大值和往左找最小值來將搜尋範圍漸漸縮小(將最大和最小的設為基準點),如果資料為大多排好的情況,則只要往左和往右找幾次就能排好了。

  3. 選擇
    平均: O(n2)
    依序將最小值往array的最前面放。從index為0開始,找"index~最後"之中的哪個值為最小,與前面的值互換,接著index + 1,重複以上步驟,最後把值從小排到大。

  4. 插入
    平均: O(n2)
    分為往後和往前遍歷,往後的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)
arr = [1, 2, 3, 5, 6] def find(source, target): for data in range(arr): if data == source: return data return None
  1. 二分搜尋法 O(logn)
    首先此陣列要先"排序",接著不停地找中位數,比較我要找的值比中位數更大或更小,接著不停地比對該值,直到找到該數值為止。

  2. 最大/最小搜尋法 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演算法加密金鑰
  • 私密金鑰: 接收方自己的金鑰,不傳給他人
  1. 主要運作原理:
    接受方擁有公開和私密的金鑰。要傳送資料前,將公開金鑰傳給傳送方,傳送方將資料加密之後傳給接受方,再用私密的金鑰來解密。

  2. 可能的威脅: 中間人攻擊

簡單來說,就是駭客用自己的公開金鑰(姑且稱為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群,並"隨機挑選"群集的中心點,接著計算"群集中每個點到中心點"最短距離,"重新計算"該中心點的新位置來做"重新分群",直到每個群集的每個點已經不再變化,表示最佳的分群已經完成。
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