【算法】算法圖解筆記_算法簡介

tomlingtm 發布于2019-07-31 10:10 / 1303人閱讀

摘要：在本書中你將學習比較不同算法的優缺點該使用合并排序算法還是快速排序算法或者該使用數組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。

在讀《算法圖解》這本書，這本書有兩個優點：

手繪風格的圖，看著很讓人“入戲”；

算法采用Python語言描述，能更好的表達算法思想。

關于算法的學習有兩點心得：

算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細節上。
比如，本書的快速排序，使用了列表推導式，很簡單就把算法的思想描述了出來。相比而言，某些使用C語言的書籍給出的版本則比較難懂，歸其原因是因為太突出細節了。細節不是不重要，而是我們要首先把算法能更好地理解，下一步才是實現和優化。

某些情況下遞歸比迭代更容易表達算法
遞歸是描述性的，側重了對算法性質的表達；而迭代更側重算法實現，往往摻雜了太多的實現細節。所以，我同時用Haskell給出遞歸版本的算法描述。

好了，開始。

引言

算法是一組完成任務的指令。任何代碼片段都可視為算法。
[注意：該書對算法的定義與通行的定義不同，通行的定義要求算法應該具有有窮性，即算法必須能在執行有限個步驟之后終止，否則算法是沒有意義的。]

在本書中,你將學習比較不同算法的優缺點:該使用合并排序算法還是快速排序算法,或者該使用數組還是鏈表。僅僅改用不同的數據結構就可能讓結果大不相同。

二分查找（binary search）

其輸入是一個有序的元素列表;查找的元素包含在列表中,二分查找返回其位置;否則返回 Nothing。
一般而言,對于包含n個元素的列表,用二分查找最多需要log2n步。

Python版本：

def binary_search(list, item):
    low = 0
    high = len(list)—1
    
    while low <= high:
        mid = (low + high)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

Haskell版本：使用了Vector，因為標準庫的列表是單鏈表，不支持隨機訪問。

import qualified Data.Vector as V

binarySearch :: (Ord a)=>  V.Vector a -> Int -> Int -> a -> Maybe Int
binarySearch vec low high e
          | low > high = Nothing
          | vec V.! mid < e = binarySearch vec (mid+1) high e
          | vec V.! mid > e = binarySearch vec low (mid-1) e
          | otherwise = Just mid
          where
              mid = low + ((high-low) `div` 2)

大 O 表示法

僅知道算法需要多長時間才能運行完畢還不夠,還需知道運行時間如何隨列表增長而增加。

算法的運行時間以不同的速度增加

算法的速度指的并非時間,而是操作數的增速。談論算法的速度時,我們說的是隨著輸入的增加,其運行時間將以什么樣的速度增加。大 O 表示法讓你能夠比較操作數,它指出了算法運行時間的增速。

大 O 表示法指出了最糟情況下的運行時間

這是一個保證——如，簡單查找的運行時間不可能超過O(n)。

一些常見的大 O 運行時間

? O(log n),也叫對數時間,這樣的算法包括二分查找。
? O(n),也叫線性時間,這樣的算法包括簡單查找。
? O(n * log n),這樣的算法包括快速排序——一種速度較快的排序算法。
? O(n2),這樣的算法包括選擇排序——一種速度較慢的排序算法。
? O(n!),這樣的算法包括旅行商問題的解決方案——一種非常慢的算法

旅行商問題

旅行商要前往n個城市,同時要確保旅程最短，時間復雜度：O(n!)。

請關注我的公眾號哦。

云服務器 GPU云服務器排序算法圖解云計算_算法數據結構算法算法字符串處理算法匹配算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43380.html

【算法】算法圖解筆記_遞歸

遞歸是個有意思的概念，正如在前面所說，遞歸能讓算法的可讀性大大提高，而且通常要比使用循環結構更能寫出準確的算法。這本書形象引入了遞歸，并沒有太深入，所以我進行了一點添油加醋。遞歸概念遞歸其實就是自己調用自己。可以從多種維度對遞歸分類，我見過的最常見的分類：直接遞歸自己直接調用自己。如： --haskell length :: [a] -> Int length [] = 0 length...

tomlingtm 2019-07-31 10:12 評論0 收藏0
【算法】算法圖解筆記_選擇排序

摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數據時有兩種基本方式數組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。選擇排序是下一章將介紹的快速排序的基石。內存的工作原理計算機就像是很多抽屜的集合體,每個抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 評論0 收藏0
【算法】算法圖解筆記_廣度優先搜索

摘要：解決最短路徑問題的算法被稱為廣度優先搜索。廣度優先搜索算法最早由年在如何從迷宮中尋找出路這一問題中提出。廣度優先搜索讓你能夠找出兩樣東西之間的最短距離。使用廣度優先搜索解決問題。你經常需要解決最短路徑問題(shorterst-path problem)。解決最短路徑問題的算法被稱為廣度優先搜索。廣度優先搜索算法最早由Edward F. Moore 1959年在如何從迷宮中尋找出路這一...

sanyang 2019-07-31 10:18 評論0 收藏0
【算法】算法圖解筆記_快速排序

摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為。快速排序和合并排序的算法速度分別表示為和，是算法所需的固定時間量被稱為常量。分而治之分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 評論0 收藏0