《演算法圖解》讀書筆記—像小說一樣有趣的演算法入門書

摘要： 前言 學習演算法課程的時候，老師推薦了兩本演算法和資料結構入門書，一本是《演算法圖解》、一本是《大話資料結構》，《演算法圖解》這本書最近讀完了，讀完的最大感受就是對演算法不再感到畏懼和陌生，對常用的演算法和資料結構都會在心裡有個基本的概念，這篇文章記錄下這本書的主要內...

前言

學習演算法課程的時候，老師推薦了兩本演算法和資料結構入門書，一本是《演算法圖解》、一本是《大話資料結構》，《演算法圖解》這本書最近讀完了，讀完的最大感受就是對演算法不再感到畏懼和陌生，對常用的演算法和資料結構都會在心裡有個基本的概念，這篇文章記錄下這本書的主要內容和知識點。

總的來說，這本書是一本不錯的演算法入門書，作者以從實際開發場景出發，介紹了軟體開發中最基本、最常用的一些 資料結構 和 演算法思想 ，同時作者寫得非常深入淺出，聯絡實際應用場景，並結合了大量的演算法推演圖示，舉例生動形象，循序漸進，使讀者易於理解，能夠很大地培養讀者對演算法的興趣，從而引導讀者進一步地進行學習研究。

正如作者在書開頭 關於本書 中所說，閱讀這本書 最佳姿勢 是從頭到尾讀，因為作者對內容順序專門做了精心地編排，從簡到難。前三章是最基礎的部分，第一章通過 二分查詢 演算法來引出衡量演算法優劣的 大O表示法 概念，同時介紹了 陣列 和 連結串列 這兩種最基本的資料結構，通過這兩種最基本的資料結構，可以來建立更高階更復雜的資料結構，第三章則介紹了 遞迴 ，一種被眾多演算法（如快速排序）採用的程式設計技巧。

從第四章開始，介紹地都是應用特別廣泛的一些演算法，第四章介紹了 快速排序 ，一種效率最高的排序演算法。第五章介紹了 散列表 ，也叫雜湊表或者字典，介紹了雜湊表的實現，怎麼解決衝突，應用場景等內容。第六七章主要介紹的是 圖 這種資料結構，有向圖還是無向圖，帶權值還是不帶權值，以及和圖相關的幾種演算法， 廣度優先演算法 和 狄克斯特演算法 。第八章介紹了 貪婪演算法 ，在沒有高效的解決方案是，可以考慮用 貪婪演算法 來得到近似答案。第九章介紹的是 動態規劃 ，第十章介紹一種簡單的機器學習演算法 K 最近鄰演算法 ，可以應用於建立推薦系統、OCR引擎、預測股價以及物體分類等領域，最後一章介紹了其他一些解決特定問題的常見演算法。

二分查詢

二分查詢解決的是 如何最快地在一個有序的集合中找到一個目標數的問題 。使用二分查詢，每次都折半，通過和中間大的數比對，縮小範圍，最終只需要 O(logn) 的事件複雜度。

/*
二分查詢
array：有序陣列
target: 目標數
loopCount: 尋找次數
return: 目標數下標
 */
- (NSInteger)binarySearchSortInArray:(NSArray<NSNumber *> *)array target:(NSNumber *)target loopCount:(NSInteger *)loopCount
{
NSInteger low = 0;
NSInteger high = array.count - 1;

while (low <= high) {
NSInteger mid = (low + high) / 2;
NSInteger guess = array[mid].integerValue;
*loopCount = *loopCount + 1;
if (guess == target.integerValue) {
// 猜中了
return mid;
}

if (guess < target.integerValue) {
// 猜小了
low = mid + 1;
} else {
// 猜大了
high = mid - 1;
}
}

return -1;
}

// 測試資料 -----------------------------------------------------
NSArray *array = @[@1, @2, @5, @6, @9, @10, @13, @18, @22, @30];
NSInteger loopCount = 0;
NSInteger result = [self binarySearchInSortArray:array target:@2 loopCount:&loopCount];
if (result >= 0) {
NSLog(@"找到目標數，目標數的的下標是：%ld，尋找：%ld 次", result, (long)loopCount);
} else {
NSLog(@"沒有找到找到目標數，目標數的的下標是：%ld, 尋找：%ld 次", result, (long)loopCount);
}

// 列印日誌 ------------------------------------------------------
找到目標數，目標數的的下標是：1，尋找：2 次

複製程式碼

遞迴

遞迴是一種自己呼叫自己的函式，每個遞迴有兩個條件，分別是 基線條件 和 遞迴條件 。如著名的斐波那契數列，在數學上，就是可以用 遞推公式 來表示這個數列。

在程式設計領域，是常被很多演算法所採用的一種程式設計技巧。如上面的二分查詢也可以使用遞迴來寫：

int binary_search(int nums[], int target, int low, int high)
{
if(low > high) {return low;} // 基線條件
int mid = low + (high - low) / 2;
if(nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
// 中間值大於目標值，遞迴條件
return binary_search(nums, target, low, mid - 1);
} else {
// 中間值小於目標值，遞迴條件
return binary_search(nums, target, mid + 1, high);
} 
}

// 測試 -----------------------------------------------------
int array[10] = {1, 2, 5, 6, 9, 10, 13, 18, 22, 30};
int result = binary_search(array, 9, 0, sizeof(array)/sizeof(int));
printf("result = %d", result); // result = 4
複製程式碼

排序

#選擇排序

選擇排序的思想是，每次都從陣列中選擇最小的數然後依次從起始的位置開始存放，有兩層迴圈，所以時間複雜度是 n^2。

// 選擇排序
void select_sort(int nums[], int length)
{
int a = nums[0];
// n -1 輪選擇
for(int i = 0; i < length - 1; i++)
{
// 最小值所在索引
int min_index = i;
for(int j = i + 1; j < length; j++)
{
if(nums[min_index] > nums[j]) {
// 有更小的
min_index = j;
}
}

// 如果正好，就不用交換
if (i != min_index) {
// 交換位置
int temp = nums[i];
nums[i] = nums[min_index];
nums[min_index] = temp;
}
}
}

// 測試資料 ------------------------------------------
int a[10] = {12, 7, 67, 8, 5, 199, 78, 6, 2, 1};
select_sort(a, 10);

for(int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}

// 列印日誌 -----------------------------------------
1 2 5 6 7 8 12 67 78 199 

複製程式碼

#快速排序

快速排序是最快的一種排序演算法，使用遞迴的思路，每次從陣列中找出一個基準點，將陣列分割成三分部分，小於所有基準點的元素組成一個數組less，大於基準點的元素組成一個數組greater，less + 基準點 + greater 就是新的陣列，小陣列也按照這種思路選取基準點進行分割，遞迴下去，遞迴的基線條件是陣列的長度小於 2 時停止，意味著陣列不能再分割下去了。這種思路下排序的時間複雜度是O(nlogn)。

// 快速排序
func quickSort(_ array:[Int]) -> [Int]
{
if array.count < 2 {
// 基線條件
return array;
} else {
// 遞迴條件
let pivot = array[0]
let less = array.filter{$0 < pivot}
let greater = array.filter{$0 > pivot}

return quickSort(less) + [pivot] + quickSort(greater)
}
}

// 測試
var array = [1, 78, 8, 76, 98, 90, 3, 100, 45, 78]
var newArray = quickSort(array)
// 列印
print(newArray) // [1, 3, 8, 45, 76, 78, 90, 98, 100]
複製程式碼

散列表

散列表 是一種非常常見的資料結構，通過 陣列 結合 雜湊函式 實現，雜湊函式計算出值所對應的陣列下標對映，在其他一些平臺上也被稱為雜湊對映、對映、字典和關聯陣列，能做到 O(1) 平均複雜度的訪問、插入和刪除操作，是一種比較底層的資料結構。

散列表常用於查詢、去重、快取等應用場景，幾乎每種程式語言都有自己的散列表實現，如 Objective-C 的 NSDictionary，要想散列表有較好的效能和避免衝突（兩個鍵對映到了同一個位置），意味著需要有 較低的填裝因子（散列表包含的元素數/佔用儲存的位置總數） 和 良好的雜湊函式 。

一個不錯的經驗是，一旦填裝因子大於0.7，就要調整散列表的長度。而一旦發生衝突的一種解決辦法是，在衝突的位置儲存一個連結串列，將多個值儲存到連結串列的不同的節點上，這樣訪問的時候就還需要從頭遍歷一遍該位置的連結串列才行，好的雜湊函式應該是 將鍵均勻的對映到散列表的不同位置 。

leetCode上第一道兩數之和的題目就可以使用散列表來降低演算法的時間複雜度。

/*
 * @lc app=leetcode.cn id=1 lang=swift
 *
 * [1] 兩數之和
 *
 * https://leetcode-cn.com/problems/two-sum/description/
 *
 * algorithms
 * Easy (44.51%)
 * Total Accepted:243.9K
 * Total Submissions: 548K
 * Testcase Example:'[2,7,11,15]\n9'
 *
 * 給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，並返回他們的陣列下標。
 * 
 * 你可以假設每種輸入只會對應一個答案。但是，你不能重複利用這個陣列中同樣的元素。
 * 
 * 示例:
 * 
 * 給定 nums = [2, 7, 11, 15], target = 9
 * 
 * 因為 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 * 
 * 
 */
 
// C 兩層迴圈實現
int* twoSum(int* nums, int numsSize, int target) {
static int resultArray[2];
for (int i = 0; i < numsSize; i ++) {
for (int j = i + 1; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
resultArray[0] = i;
resultArray[1] = j;
}
}
}

return resultArray;
}

// swift 使用散列表實現
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

var hash = [Int: Int]
for (index, item) in nums {
// 使用散列表來判斷元素是否在散列表中，有的話返回元素的下標，即散列表的值
if let firstIndex = hash[target - item] {
return [firstIndex, index]
}

// 將陣列元素的值當做散列表的鍵，下標當做散列表的值儲存在散列表中
hash[item] = index
}

return [-1,-1]
}
}
複製程式碼

使用散列表實現後:

廣度優先搜尋演算法(breadth-first-search，BFS)

廣度優先搜尋 要解決的問題是基於 圖 這種資料結構的 最短路徑 的問題。是一種 用於圖的查詢演算法 ，可幫助回答兩類問題：

1. 從頂點 a 出發，有前往頂點 b 的路徑嗎？
2. 從頂點 a 出發，前往頂點 b 的哪條路徑最短？

再看一下 圖 的定義：

圖（Graph）是由 頂點 的 有窮非空集合 和 頂點之間邊的集合 組成，通常表示為：G(V,E)，其中，G 表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。

圖有很多種類：

• 按照有無方向可以分為 有向圖 和 無向圖 ，有向圖的邊又稱為 弧 ，有 弧頭 和 弧尾 之分。
• 按照邊或弧的多少又分為 稀疏圖 和 稠密圖 。如果任意兩個頂點之間都存在邊叫做 完全圖 ，邊有向的叫做 有向完全圖 ，若無重複的邊或者頂點到自身的邊叫做 簡單圖 。
• 圖上的邊或者弧帶上權則叫做 網 。

可以得出結論， 廣度優先搜尋 解決問題的資料模型是有向圖，且不加權。

書中列舉了兩個列子，先來看第一個， 如何選擇換乘公交最少的路線？ ，假設你住在舊金山，現在要從雙子峰前往金門大橋，如圖所示：

可以從圖中得知，到達金門大橋最少需要三步，最短路徑是從雙子峰步行到搭乘 44 路公交，然後再換乘 28 路公交最短。

第二個例子是這樣的，假設你經營一個芒果農場，需要尋找芒果銷售商，如何在你自己的朋友關係網中找到芒果銷售商，這種關係包括你自己的朋友，這個是一度關係，也包括朋友的朋友，這個是二度關係，依次類推，那怎麼找到最短路徑呢？

解題思路：

使用 散列表 來儲存關係網，使用 佇列 來儲存查詢順序，優先查詢一度關係，再二度關係，依次類推。然後遍歷佇列判斷是否是芒果銷售商，是的話就是最近的芒果銷售商，如果不是，再查詢二度關係，如果最後都沒有找到就是關係網裡面沒有芒果銷售商。

swift 實現程式碼如下：

// 1. 使用陣列來實現一個佇列，先進先出
struct Queue<Element> {
private var elements: [Element] = []

init() {

}

var count: Int {
return elements.count
}

var isEmpty: Bool {
return elements.isEmpty
}

// 佇列第一個元素
var peek: Element? {
return elements.first
}

// 入隊
mutating func enqueue(_ element:Element) {
elements.append(element)
}

// 出隊
mutating func dequeue() -> Element?{
return isEmpty ? nil : elements.removeFirst()
}
}

extension Queue: CustomStringConvertible {
var description: String {
return elements.description
}
}

// 2. 使用散列表來儲存關係網
var graph = [String:Any]()
// 一度關係
graph["you"] = ["claire", "bob", "alice"]
// 二度關係
graph["bob"] = ["anuj", "peggy"]
graph["claire"] = ["thom", "jonny"]
graph["alice"] = ["peggy"]
// 三度關係
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

// 3. 廣度優先搜尋演算法
func search(_ name: String, inGraph g: [String:Any]) -> Bool {
// 搜尋隊列
var searchQueue = Queue<String>()
// 入佇列
for item in g[name] as! Array<String> {
searchQueue.enqueue(item)
}

// 記錄已經查詢過的人
var searched = [String]()
// 迴圈結束條件 1. 找到一位芒果銷售商；2. 佇列為空，意味著關係網裡面沒有芒果銷售商
while !searchQueue.isEmpty {
// 出隊
let person = searchQueue.dequeue()
// 判斷是否已經檢查過，檢查過就不再檢查，防止出現死迴圈
if !searched.contains(person!) {
if personIsSeller(person!) {
print("找到了芒果銷售商:\(person!)")
return true
} else {
// 尋找下一度關係
// 入佇列
for item in g[person!] as! Array<String> {
searchQueue.enqueue(item)
}

// 將這個人標記檢查過
searched.append(person!)
}
}
}

// 迴圈結束，沒有找到
return false
}

// 是不是銷售商，規則可以隨便設定
func personIsSeller(_ name: String) -> Bool {
if let c = name.last {
return c == "y"
}

return false
}

// 測試
search("you", inGraph: graph) // 找到了芒果銷售商:jonny
search("bob", inGraph: graph) // 找到了芒果銷售商:peggy
複製程式碼

狄克斯特演算法

深度優先演算法BFS適用於 無加權圖 ，找出的最短路徑是邊數最少的路徑，而 狄克斯特演算法 解決的是 加權圖 中的 最短路徑 問題，找出的是最經濟最划算的路徑。

注意：狄克斯特演算法也不適用於帶環的圖，只適用於 有向無環圖 ，也不適用於 負權邊 的圖，負權邊的圖的最短路徑問題可以使用貝爾曼-福德演算法。

狄克斯特演算法 包含四個步驟：

1. 找出最便宜的頂點，即可在最少權重內到達前往的頂點；
2. 對於該頂點的鄰居，檢查是否有前往他們的更短路徑，如果有，就更新其開銷；
3. 重複這個過程，直到圖中的每個頂點都這樣做了；
4. 計算最終路徑；

書中舉了一個換鋼琴的例子，如何用樂譜再加最少的錢換到鋼琴的問題，使用 狄克斯特演算法 的解決思路是：

解題思路：

一、找出最便宜的節點，樂普的鄰居是唱片和海報，換唱片要支付 5 美元，換海報不用錢。先建立一個表格，記錄每個節點的開銷以及父節點。所以下一個最便宜的節點是海報。

二、計算前往該節點的各個鄰居節點的開銷。第一步中海報最便宜，所以先從海報出發，海報可以換吉他需要加 30 美元，還可以換架子鼓需要加 35 美元，再計算黑膠唱片，黑膠唱片可以換吉他需要加 15 美元，還可以換架子鼓需要加 20 美元，和第一步的相加可以算出，通過黑膠唱片這條路徑前往，開銷最短，更新上一步中最便宜的節點為黑膠唱片。從樂普換吉他最少需要花 20 美元，換架子鼓最少需要花 25 美元。所以下一個最便宜的節點是海報。

三、優先從吉他出發，計算其鄰居節點開銷。吉他的鄰居就是鋼琴，需要加 20 美元，總開銷加上之前的 20 美元是 40 美元，再從架子鼓出發，計算架子鼓到其鄰居節點的開銷，架子鼓的鄰居節點也是鋼琴，開銷 10 美元，加上之前的 25 美元總開銷是 35 美元，所以更新最優節點是架子鼓。

最終路徑是從樂譜->黑膠唱片->架子鼓->鋼琴。

演算法實現

需要三個散列表，一個用來儲存整個圖結構，一個用來儲存節點的開銷，最後一個用來儲存節點的父節點。演算法執行流程圖：

// 狄克斯特搜尋演算法
// 引數g：圖形結構散列表
// costs:節點開銷散列表 inout 關鍵字可以是得函式內部可以修改外部引數的值
// parents: 父節點散列表
// targetNode:目標節點
// 返回值：（總的最少花銷，最短路徑步驟，排序陣列）
func search(costs:inout [String :Int], parents:inout [String: String?], targetNode: String, inGraph g: [String : Any]) ->(Int, String)
{
// 儲存處理過的節點
var processed = [String]()

// 找出最便宜的節點
func findLowerCostNode(_ costs: [String:Int]) -> String? {
var lowestCost = Int.max
var lowerCostNode: String?
for (key, value) in costs {
// 遍歷開銷散列表，找出沒有處理過且到起點花費最小開銷的節點
if value < lowestCost && !processed.contains(key){
lowestCost = value
lowerCostNode = key
}
}

return lowerCostNode
}

var node = findLowerCostNode(costs)
// 遍歷所有的節點
while (node != nil) {
// 節點開銷
let cost = costs[node!]
// 遍歷當前節點的所有的鄰居節點
var neighbors = graph[node!]
for n in (neighbors?.keys)! {
// 判斷該鄰居節點如果從當前節點經過的總開銷是否小於該鄰居節點原來的開銷，如果小於，就更新該鄰居節點的開銷
let new_cost = cost! + (neighbors?[n])!
if costs[n]! > new_cost {
// 更新該節點的鄰居節點的最新最短開銷
costs[n] = new_cost
// 更新該鄰居節點的父節點為當前節點
parents[n] = node!
}
}

// 將當前節點標記為已經處理過的節點
processed.append(node!)
// 繼續尋找下一個最少開銷且未處理過的節點
node = findLowerCostNode(costs)
}

// 到達目標節點的最少開銷
let minCost = costs[targetNode]
// 最短路徑
var minRoadArray = [targetNode]
var parent:String? = targetNode
while parents[parent!] != nil {
parent = parents[parent!]!
minRoadArray.append(parent!)
}

return (minCost!, minRoadArray.reversed().joined(separator: "->"))
}


// 測試 ————————————————————-------------------------------------------
// 1. 儲存圖結構
var graph = [String : Dictionary<String, Int>]()

// 樂譜的鄰居節點
graph["樂譜"] = [String : Int]()
// 到唱片的開銷
graph["樂譜"]?["黑膠唱片"] = 5
// 到海報的開銷
graph["樂譜"]?["海報"] = 0

// 唱片節點的鄰居節點
graph["黑膠唱片"] = [String : Int]()
// 唱片節點到吉他的開銷
graph["黑膠唱片"]?["吉他"] = 15
// 唱片節點到架子鼓的開銷
graph["黑膠唱片"]?["架子鼓"] = 20

// 海報節點的鄰居節點
graph["海報"] = [String : Int]()
// 海報節點到吉他的開銷
graph["海報"]?["吉他"] = 30
// 海報節點到架子鼓的開銷
graph["海報"]?["架子鼓"] = 35

// 吉他節點的鄰居節點
graph["吉他"] = [String : Int]()
// 吉他節點到鋼琴的開銷
graph["吉他"]?["鋼琴"] = 20


// 架子鼓節點的鄰居節點
graph["架子鼓"] = [String : Int]()
// 架子鼓節點到鋼琴的開銷
graph["架子鼓"]?["鋼琴"] = 10

// 鋼琴節點
graph["鋼琴"] = [String : Int]()

print(graph)

// 2. 建立開銷表，表示從樂譜到各個節點的開銷
var costs = [String : Int]()
// 到海報節點開銷
costs["海報"] = 0
// 到黑膠唱片節點開銷
costs["黑膠唱片"] = 5
// 到鋼琴節點開銷，不知道，初始化為最大
costs["吉他"] = Int.max
// 到鋼琴節點開銷，不知道，初始化為最大
costs["架子鼓"] = Int.max
// 到鋼琴節點開銷，不知道，初始化為最大
costs["鋼琴"] = Int.max

print(costs)

// 3. 建立父節點表
var parents = [String : String?]()
// 海報節點的父節點是樂譜
parents["海報"] = "樂譜"
// 黑膠唱片的父節點是樂譜
parents["黑膠唱片"] = "樂譜"
// 吉他的父節點，不知道
parents["吉他"] = nil
// 架子鼓的父節點，不知道
parents["架子鼓"] = nil
// 鋼琴的父節點， 不知道
parents["鋼琴"] = nil

print(parents)

// 測試
var (minCost, minRoadString) = search(costs: &costs, parents: &parents, targetNode: "鋼琴", inGraph: graph)

複製程式碼

列印日誌：

貪婪演算法

貪婪演算法 是一種通過尋找 區域性最優解來試圖獲取全域性最優解 的一種易於實現、執行速度快的 近似演算法 。是解決 NP 完全問題（沒有快速演算法問題） 的一種簡單策略。書上總共舉了四個例子來說明 貪婪演算法 的一些場景。

1. 教師排程問題

有如下課程表，要怎麼排課排程，使得有儘可能多的課程安排在某間教室上。

這個問題就可以使用 貪婪演算法 來解決。

1. 選出結束最早的課，他就是要在這件教室上的第一節課。
2. 接著，選擇第一節課結束後才開始的課，同樣選擇結束最早的課，這就是要在這件教室上的第二節課。重複這樣做，就能找出答案。

2. 揹包問題

這個問題是這樣的，如何在容量有限的揹包中裝入總價值最高的商品。這個問題不適用 貪婪演算法 ，按照貪婪演算法，每次都需要往揹包裡先裝最大價值的商品，然後根據揹包剩餘容量，再選擇最大價值的商品，這樣有可能揹包的 空間利用率不是最高的 ，卻不一定會是最優解。

2. 集合覆蓋問題

背景是這樣的，有個廣播節目，要讓全美 50 各州的聽眾都能聽到，需要在選出覆蓋全美 50 各州的最小廣播臺集合。如果要需求最優解，可能的子集有 2^n 次方個，如果個廣播臺很多，那麼這個演算法的複雜度將非常之高，幾乎沒有任何演算法可以足夠快速的解決這個問題，而使用貪婪演算法可以快速的找到近似解，演算法的複雜度是 O(n^2)。步驟如下：

1. 選擇一個覆蓋最多未覆州的廣播臺，即時已經覆蓋了一些已經覆蓋過的州也沒關係。
2. 重複第一步，知道覆蓋了所有的州。

程式碼模擬實現：

// 要覆蓋的州列表
var statesNeeded = Set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

// 廣播臺清單
var stations= [String: Set<String>]()
stations["kone"] = Set(["id", "nv", "ut"])
stations["ktwo"] = Set(["wa", "id", "mt"])
stations["kthree"] = Set(["or", "nv", "ca"])
stations["kfour"] = Set(["nv", "ut"])
stations["kfive"] = Set(["ca", "az"])

// 最終選擇的廣播臺集合
var finalStations = Set<String>()

// 如果要覆蓋的州列表不為空
while !statesNeeded.isEmpty {
// 覆蓋了最多沒覆蓋州的廣播臺
var bestStation:String?
// 已經覆蓋了的州的集合
var statesCovered = Set<String>()
// 遍歷所有的廣播臺
for (station, states) in stations {
// 取交集操作
let covered = statesNeeded.intersection(states)
if covered.count > statesCovered.count {
bestStation = station
statesCovered = covered
}
}

// 取差集操作
statesNeeded = statesNeeded.subtracting(statesCovered)
finalStations.insert(bestStation!)
}

// 列印
print(finalStations) // ["ktwo", "kfive", "kone", "kthree"]
複製程式碼

對比一下兩種演算法的執行效率差異：

3. 旅行商問題

旅行商問題的背景是一個旅行商商想要找出前往若干個城市的最短路徑，如果城市數量少，比如兩個，可能的路徑有 2 條，三個城市有 有 6 條，4 個城市有 24 條，5 個城市有 120 條，n 個城市有 n! 個可能路線，n! 複雜度是一種非常難以快速找出最優解的問題。就可以考慮 貪婪演算法 快速地去求 近似解 。

4. 如何判斷 NP 完全問題

上面的集合覆蓋問題和旅行商問題都是 NP 完全問題 ，如果能夠判斷出問題屬於 NP 完全問題，就可以考慮貪婪演算法求近似解的策略了，但是判斷 NP 完全問題並不容易，作者歸納了一些常見場景：

1. 隨著元素增加，速度會變得非常慢。
2. 涉及 所有組合 的問題通常是 NP 完全問題。
3. 不能將問題分成小問題，必須考慮各種可能的情況。也可能是 NP 完全問題。
4. 如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，可能就是 NP 完全問題。
5. 如果問題涉及集合（如廣播臺集合的例子）且難以解決，可能就是 NP 完全問題。
6. 如果問題可轉換成 集合覆蓋問題 或者 旅行商問題 ，那肯定是 NP 完全問題。

動態規劃

動態規劃 常用來解決一些在 給定約束條件下 的最優解問題，如揹包問題的約束條件就是揹包的容量，一般可以 將大問題分解為彼此獨立且離散的小問題 時，可以通過使用網格，每個小網格就是分解的小問題的手段的方式來解決。使用 動態規劃 來解決的實際問題場景有：

動態規劃

K 最近鄰演算法

KNN 用來分類和迴歸，分類是編組，迴歸是預測一個結果。通過特徵抽取，大規模訓練，然後比較資料之間的相似性，從而分類或是預測一個結果。有如下常見應用場景：

樸素貝葉斯分類器

其他一些演算法介紹

1. 樹，二叉查詢樹，左子節點的值總比自己小，右子節點的值總比自己大，可以用來優化陣列插入和刪除的複雜度底的問題，二叉查詢樹的查詢、插入、刪除的複雜度都是O(logn)。
2. 反向索引。一種將單詞對映到包含他的頁面的資料結構，可用於建立 搜尋引擎 。
3. 傅立葉變換。傅立葉變換可以將數字訊號中的各種頻率分離出來，可計算歌曲中每個音符對整個音樂的貢獻，用來做音樂壓縮，音樂識別等。
4. 並行演算法。利用裝置的多核優勢，提高演算法的執行效能。也會有一些額外開銷，如並行性管理和負載均衡。
5. MapReduce。一種分散式並行演算法，可讓演算法在多臺計算機上執行，非常適合用於在短時間內完成海量工作，MapReduce的兩個概念，對映（map）和歸併（reduce）函式。對映（map）是將序列中的元素都執行一種處理然後返回另一個序列，歸併（reduce）是序列歸併為一個元素。MapReduce 使用這個兩個概念在多臺計算機上執行資料查詢，能極大的提高速度。
6. 布隆過濾器和 HypelogLog。布隆過濾器是一種 概率性資料結構 ，有點在於 佔用空間小 ，非常適用於不要求答案絕對準確的情況。HypelogLog 近似地計算集合中不同的元素數，也是類似於布隆過濾器的一種概率性演算法。
7. SHA 演算法。SHA 演算法是一種安全雜湊演算法，給定一個字串，SHA 演算法返回其雜湊值，可用來比較檔案，檢查密碼。
8. 區域性敏感雜湊演算法。Simhash 是一種 區域性敏感雜湊演算法 。如果字串只有細微的差別，那麼雜湊值也只存在細微的差別，這就能夠用來通過比對雜湊值來判斷兩個字串的相似程度，也很有用。
9. Diffie-Hellman 祕鑰交換演算法。可用來解決 如何對訊息加密後只有收件人能看懂的問題 。這個種演算法使用兩個祕鑰，公鑰和私鑰，公鑰是公開的，傳送訊息使用公鑰加密，加密後的訊息只有使用私鑰才能解密。通訊雙方無需知道加密演算法，要破解比登天還難。
10. 線性規劃。線性規劃演算法用於在 給定約束條件下最大限度地改善指定的指標 。線性規劃使用 Simplex 演算法，是一種非常寬泛的演算法，如所有的圖演算法都可以用線性規劃來實現，圖問題只是線性規劃的一個子集。

分享個人技術學習記錄和跑步馬拉松訓練比賽、讀書筆記等內容，感興趣的朋友可以關注我的公眾號「青爭哥哥」。