《圖解算法》中常見算法總結

目錄：

1. 二分查找

2. 選擇排序

3. 遞歸&分治

4. 快速排序

5. 廣度優先搜尋

6. 狄克斯特拉算法

7. 貪婪算法（近似算法）

8. 動态規劃

9. K最近鄰算法

1.二分查找

思路：

二分查找是一種算法，其輸入是一個有序的元素清單。如果要查找的元素包含在清單中，二分查找傳回其位置；否則傳回null。

特點：

使用二分查找時，你猜測的是中間的數字，進而每次都将餘下的數字排除一半。

時間複雜度：

一般而言，對于包含n個元素的清單，用二分查找最多需要log2n步，而簡單查找最多需要n步。

python實作：

def binary_search(list,item):
    '''二分查找'''
    low=0 #起點
    high=len(list)-1 #終點
    while high>=low:
        mid=low+int((high-low)/2) #中間值
        if item==list[mid]:
            return mid
        elif item>list[mid]:
            low=mid+1;
        else:
            high=mid-1;
    return None
list=[1,2,3,6,9,10]
print(str(binary_search(list,6)))
print(str(binary_search(list,4)))
           

2.選擇排序

思路：

周遊這個清單，找出最小值，并将該最小值添加到一個新清單中。

再次這樣做，找出第二小的值。

繼續這樣做，将得到一個有序清單。

時間複雜度：

要找出最小值，必須檢查清單中的每個元素，這需要的時間為O(n)。是以對于這種時間為O(n)的操作，你需要執行n次。

需要的總時間為 O(n × n)，即O(n^2)。

python實作：

def findsmallest(arr):
    '''找清單中最小值'''
    smallest=arr[0]
    smallest_index=0
    for i in range(1,len(arr)):
        if arr[i]<smallest:
            smallest=arr[i]
            smallest_index=i
    return smallest_index
def selectionsort(arr):
    '''選擇排序'''
    new_arr=[]
    for i in range(0,len(arr)):
        smallest_index=findsmallest(arr)
        new_arr.append(arr.pop(smallest_index))
    return new_arr
print(selectionsort([1,5,4,2]))
           

3.遞歸算法&分治思想

• 遞歸：

  思想：

  每個遞歸函數都有兩部分：基線條件（base case）和遞歸條件（recursive case）。

  遞歸條件指的是函數調用自己，而基線條件則指的是函數不再調用自己，進而避免形成無限循環。

  特點：

  遞歸隻是讓解決方案更清晰，并沒有性能上的優勢。

• 分治：

  思想：

  遞歸式問題解決方法（divide and conquer， D&C）

  使用D&C解決問題的過程包括兩個步驟：

  (1) 找出基線條件，這種條件必須盡可能簡單。

  (2) 不斷将問題分解（或者說縮小規模），直到符合基線條件。

  舉例：

  （1）假設你要将一塊地均勻地分成方塊，且分出的方塊要盡可能大：

  首先，找出基線條件。最容易處理的情況是，一條邊的長度是另一條邊的整數倍。

  

  你可以從這塊地中劃出兩個640 m×640 m的方塊，同時餘下一小塊地。現在是頓悟時刻：何不對餘下的那一小塊地使用相同的算法呢？

  最初要劃分的土地尺寸為1680 m×640 m，而現在要劃分的土地更小，為640 m×400 m。 适用于這小塊地的最大方塊，也是适用于整塊地的最大方塊。換言之，你将均勻劃分1680 m×640 m土地的問題，簡化成了均勻劃分640 m×400 m土地的問題！

  

  （2）數字數組求和：

  第一步：找出基線條件。最簡單的數組什麼樣呢？如果數組不包含任何元素或隻包含一個元素，計算總和将非常容易。這就是基線條件。

  第二步：每次遞歸調用都必須離空數組更近一步。如何縮小問題的規模呢？計算第一個元素與剩餘元素總數的和，這縮小了問題規模。

  

4.快速排序

思想：

快速排序是一種常用的排序算法，比選擇排序快得多。例如， C語言标準庫中的函數qsort

實作的就是快速排序。快速排序也使用了D&C。

基線條件：為數組為空或隻包含一個元素。在這種情況下，隻需原樣傳回數組——根本就不用排序。

遞歸條件：

從數組中選擇一個元素，這個元素被稱為基準值（pivot）。

找出比基準值小的元素以及比基準值大的元素，這被稱為分區（partitioning）。

對于包含左邊的子數組以及右邊的子數組，快速排序知道如何将它們排序，是以隻要對這兩個子數組進行快速排序，再合并結果，就能得到一個有序數組。

python實作：

def quicksort(arr):
    '''快速排序法'''
    if len(arr)<2:
        return arr
    else:
        pivot=arr[0] 
        less=[i for i in arr[1:] if i<pivot] #清單解析
        larger=[i for i in arr[1:] if i>pivot]
        return quicksort(less)+[pivot]+quicksort(larger)
print(quicksort([1,5,3,2]))
           

時間複雜度：

快速排序的性能高度依賴于你選擇的基準值。

最糟情況：

假設你總是将第一個元素用作基準值，且要處理的數組是有序的。

你将一個元素用作基準值，并将其他的元素劃分到兩個子數組中。這涉及數組中的全部8個元素，是以該操作的時間為O(n)。在調用棧的第一層，涉及全部8個元素，但實際上，在調用棧的每層都涉及O(n)個元素。是以，完成每層所需的時間都為O(n)。

在最糟情況下，有O(n)層，是以該算法的運作時間為O(n) * O(n) = O(n^2)。

平均情況：

在這個示例中，層數為O(log n)，而每層需要的時間為O(n)。是以整個算法需要的時間為O(n) * O(log n) = O(n log n)。這就是平均情況。

隻要你每次都随機地選擇一個數組元素作為基準值，快速排序的平均運作時間就将為O(n log n)。

5.廣度優先搜尋

圖算法——廣度優先搜尋（breadth-first search， BFS），用于處理有向圖中最短路徑的問題。

思想：

借助隊列實作，先放入第一層，判斷每個元素是否是想要的，若是，結束；若不是，則将其鄰居（第二層），放入隊列末端，循環如此。

為解決有些元素重複處理的情況，可加入一個清單，列出所有處理過的，用于判斷。

舉例：

假設你經營着一個芒果農場，需要尋找芒果銷售商，以便将芒果賣給他。為此，你可在朋友中查找。

你應先在一度關系中搜尋，确定其中沒有芒果銷售商後，才在二度關系中搜尋。廣度優先搜尋就是這樣做的！在廣度優先搜尋的執行過程中，搜尋範圍從起點開始逐漸向外延伸，即先檢查一度關系，再檢查二度關系。

python實作：

from collections import deque
'''圖的形成'''
graph={}
graph["you"]=["alice","bob","claire"]
graph["bob"]=["anuj","peggy"]
graph["alice"]=["peggy"]
graph["claire"]=["thom","jonny"]
graph["anuj"]=[]
graph["peggy"]=[]
graph["thom"]=[]
graph["jonny"]=[]
print(graph)
'''廣度優先搜尋'''
def person_is_seller(name):
    '''定義一個供應商确定函數'''
    return name[-1]=="m"
def BFsearch(name):
    '''借助隊列'''
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            '''判斷是否重複'''
            if person_is_seller(person):
                print(person+" is a seller!")
                return True
            else:
                '''否的話要将其朋友拉入隊列'''
                search_queue += graph[person]
                searched.append(person)
    
    return False
print(BFsearch("you"))
           

其中，圖的形成可借助字典結構。

6.狄克斯特拉算法

狄克斯特拉算法（Dijkstra’s algorithm）也是一種圖算法，用來處理有權圖的最短路徑。

思想：

(1) 找出“最便宜”的節點，即權值最小的節點。

(2) 更新該節點的鄰居的開銷（前提是更小），即經過該節點到鄰居點的總權重。

(3) 重複這個過程，直到對圖中的每個節點都這樣做了。

(4) 計算最終路徑。

舉例：

（1）找兩點最短路徑

第一步： 找出最便宜的節點。

第二步：計算經節點B前往其各個鄰居所需的時間。

第三步：重複

找出可在最短時間内前往的節點

更新節點A的所有鄰居的開銷

（2）換鋼琴

Rama想拿一本樂譜換架鋼琴，如何花最少的錢實作這個目标。

準備工作：建立一個表格，在其中列出每個節點的開銷；還需在這個表中添加表示父節點的列。在執行狄克斯特拉算法的過程中，你将不斷更新表。

算法分析過程：

python實作：

問題：

三個表存儲：随着算法的進行，你将不斷更新散清單costs和parents

'''狄克斯特拉算法'''
'''有權圖形成'''
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}
print(graph)
'''開銷表'''
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
print(costs)
'''父節點表'''
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
print(parents)
processed=[]
'''找開銷最低的節點'''
def find_lowestcost_node(costs):
    lowestcost = infinity
    lowestcost_node = None
    for node in costs.keys():
        cost=costs[node]
        if cost < lowestcost and node not in processed:
            lowestcost = cost
            lowestcost_node = node
    return lowestcost_node
'''狄克斯特拉算法'''
node = find_lowestcost_node(costs) #找最便宜的點
while node is not None:
    cost=costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n] 
        if new_cost < costs[n]:
            costs[n] = new_cost #更新鄰居的值
            parents[n] = node
    processed.append(node)
    node = find_lowestcost_node(costs)
print(costs)
print(parents)
           

7.貪婪算法（近似算法）

• 貪婪算法：

  貪婪算法很簡單：每步都采取最優的做法。即每步都選擇局部最優解，最終得到的就是全局最優解，但得到的往往是接近于最優解的近似解。

• 近似算法：

  判斷近似算法優劣的标準如下：

  （1）速度有多快；

  （2）得到的近似解與最優解的接近程度。

• NP完全問題：

  需要計算所有的解，并從中選出最小/最短的那個。

  如果能夠判斷出要解決的問題屬于NP完全問題就好了，這樣就不用去尋找完美的解決方案，而是使用近似算法即可。

近似算法python實作：

集合覆寫問題：

假設你辦了個廣播節目，要讓各個州的聽衆都收聽得到。為此，你需要決定在哪些廣播台播出。在每個廣播台播出都需要支付費用，是以你力圖在盡可能少的廣播台播出。

每次需要周遊所有的廣播台，從中選擇覆寫了最多的未覆寫州的廣播台。

'''近似算法解決電台覆寫問題'''
'''資料輸入'''
states_needed = set(["mt","wa","or","id","nv","ut","ca","az"])
print(states_needed)
stations = {}
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"])
print(stations)
final_stations = set()
'''近似算法'''
while states_needed:
    '''每次找最優解'''
    best_station = None
    state_covered = set()
    for station,states in stations.items():
        covered = states & states_needed
        if covered > state_covered:
            best_station = station
            state_covered = covered
    states_needed -= state_covered
    final_stations.add(best_station)
print(final_stations)
           

8.動态規劃

動态規劃先解決子問題，再逐漸解決大問題，得到最優解。

舉例：

（1）背包問題：

假設你是個小偷，背着一個可裝4磅東西的背包。你可盜竊的商品有如下3件，為了讓盜竊的商品價值最高，你該選擇哪些商品？

每個動态規劃算法都從一個網格開始，背包問題的網格如下。

按行輸入值，隻可選目前行及上面行的物品。

計算每個單元格的價值時，使用的公式都相同：

（2）旅遊形成最優化：

假設你要去倫敦度假，假期兩天，但你想去遊覽的地方很多。你沒法前往每個地方遊覽，是以你列個單子。根據這個清單，你能确定該去遊覽哪些名勝嗎？

網格如下：

9.K最近鄰算法

K最近鄰（k-nearest neighbours， KNN）算法做兩項基本工作——分類和回歸：

（1）分類就是編組；

（2）回歸就是預測結果（如一個數字）。

舉例：

猜水果，是橙子還是柚子呢？我知道，柚子通常比橙子更大、更紅。

如果判斷這個水果是橙子還是柚子呢？一種辦法是看它的鄰居。來看看離它最近的三個鄰居。在這三個鄰居中，橙子比柚子多，是以這個水果很可能是橙子。

（2）建立推薦系統：

假設你是Netflix，要為使用者建立一個電影推薦系統。

方法：

你可以将所有使用者都放入一個圖表中。這些使用者在圖表中的位置取決于其喜好，是以喜好相似的使用者距離較近。假設你要向Priyanka推薦電影，可以找出五位與他最接近的使用者。

特征提取：

需要将每位使用者都轉換為一組坐标

使用者注冊時，要求他們指出對各種電影的喜歡程度。這樣，對于每位使用者，都将獲得一組數字！

這裡計算的是五維（而不是二維）空間中的距離。

（3）烤面包

假設你在伯克利開個小小的面包店，每天都做新鮮面包，需要根據如下一組特

征預測當天該烤多少條面包

你還有一些曆史資料，記錄了在各種不同的日子裡售出的面包數量。

今天是周末，天氣不錯。根據這些資料，預測你今天能售出多少條面包呢？我們來使用KNN算法，其中的K為4。首先，找出與今天最接近的4個鄰居。

最近的鄰居為A、 B、 D和E。

将這些天售出的面包數平均，結果為218.75。這就是你今天要烤的面包數！

使用到回歸。