資訊專(zhuān)欄INFORMATION COLUMN
摘要：在本書(shū)中你將學(xué)習(xí)比較不同算法的優(yōu)缺點(diǎn)該使用合并排序算法還是快速排序算法或者該使用數(shù)組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。
在讀《算法圖解》這本書(shū)，這本書(shū)有兩個(gè)優(yōu)點(diǎn)：
手繪風(fēng)格的圖，看著很讓人“入戲”；
算法采用Python語(yǔ)言描述，能更好的表達(dá)算法思想。
關(guān)于算法的學(xué)習(xí)有兩點(diǎn)心得：
算法思想最重要，理解了思想，算法是很容易寫(xiě)出來(lái)的，所以盡量不要把過(guò)多精力放在細(xì)節(jié)上。
比如，本書(shū)的快速排序，使用了列表推導(dǎo)式，很簡(jiǎn)單就把算法的思想描述了出來(lái)。相比而言，某些使用C語(yǔ)言的書(shū)籍給出的版本則比較難懂，歸其原因是因?yàn)樘怀黾?xì)節(jié)了。細(xì)節(jié)不是不重要，而是我們要首先把算法能更好地理解，下一步才是實(shí)現(xiàn)和優(yōu)化。
某些情況下遞歸比迭代更容易表達(dá)算法
遞歸是描述性的，側(cè)重了對(duì)算法性質(zhì)的表達(dá)；而迭代更側(cè)重算法實(shí)現(xiàn)，往往摻雜了太多的實(shí)現(xiàn)細(xì)節(jié)。所以，我同時(shí)用Haskell給出遞歸版本的算法描述。
好了，開(kāi)始。
引言算法是一組完成任務(wù)的指令。任何代碼片段都可視為算法。
[注意：該書(shū)對(duì)算法的定義與通行的定義不同，通行的定義要求算法應(yīng)該具有有窮性，即算法必須能在執(zhí)行有限個(gè)步驟之后終止，否則算法是沒(méi)有意義的。]
在本書(shū)中,你將學(xué)習(xí)比較不同算法的優(yōu)缺點(diǎn):該使用合并排序算法還是快速排序算法,或者該使用數(shù)組還是鏈表。僅僅改用不同的數(shù)據(jù)結(jié)構(gòu)就可能讓結(jié)果大不相同。
二分查找（binary search）其輸入是一個(gè)有序的元素列表;查找的元素包含在列表中,二分查找返回其位置;否則返回 Nothing。
一般而言,對(duì)于包含n個(gè)元素的列表,用二分查找最多需要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，因?yàn)闃?biāo)準(zhǔn)庫(kù)的列表是單鏈表，不支持隨機(jī)訪問(wèn)。
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 表示法
僅知道算法需要多長(zhǎng)時(shí)間才能運(yùn)行完畢還不夠,還需知道運(yùn)行時(shí)間如何隨列表增長(zhǎng)而增加。
算法的運(yùn)行時(shí)間以不同的速度增加算法的速度指的并非時(shí)間,而是操作數(shù)的增速。談?wù)撍惴ǖ乃俣葧r(shí),我們說(shuō)的是隨著輸入的增加,其運(yùn)行時(shí)間將以什么樣的速度增加。大 O 表示法讓你能夠比較操作數(shù),它指出了算法運(yùn)行時(shí)間的增速。
這是一個(gè)保證——如，簡(jiǎn)單查找的運(yùn)行時(shí)間不可能超過(guò)O(n)。
一些常見(jiàn)的大 O 運(yùn)行時(shí)間? O(log n),也叫對(duì)數(shù)時(shí)間,這樣的算法包括二分查找。
? O(n),也叫線性時(shí)間,這樣的算法包括簡(jiǎn)單查找。
? O(n * log n),這樣的算法包括快速排序——一種速度較快的排序算法。
? O(n2),這樣的算法包括選擇排序——一種速度較慢的排序算法。
? O(n!),這樣的算法包括旅行商問(wèn)題的解決方案——一種非常慢的算法
旅行商要前往n個(gè)城市,同時(shí)要確保旅程最短，時(shí)間復(fù)雜度：O(n!)。
請(qǐng)關(guān)注我的公眾號(hào)哦。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43380.html
遞歸是個(gè)有意思的概念，正如在前面所說(shuō)，遞歸能讓算法的可讀性大大提高，而且通常要比使用循環(huán)結(jié)構(gòu)更能寫(xiě)出準(zhǔn)確的算法。這本書(shū)形象引入了遞歸，并沒(méi)有太深入，所以我進(jìn)行了一點(diǎn)添油加醋。 遞歸 概念 遞歸其實(shí)就是自己調(diào)用自己。可以從多種維度對(duì)遞歸分類(lèi)，我見(jiàn)過(guò)的最常見(jiàn)的分類(lèi)： 直接遞歸 自己直接調(diào)用自己。如： --haskell length :: [a] -> Int length [] = 0 length...
摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲(chǔ)多項(xiàng)數(shù)據(jù)時(shí)有兩種基本方式數(shù)組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。 選擇排序是下一章將介紹的快速排序的基石。 內(nèi)存的工作原理 計(jì)算機(jī)就像是很多抽屜的集合體,每個(gè)抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...
摘要：解決最短路徑問(wèn)題的算法被稱(chēng)為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由年在如何從迷宮中尋找出路這一問(wèn)題中提出。廣度優(yōu)先搜索讓你能夠找出兩樣?xùn)|西之間的最短距離。使用廣度優(yōu)先搜索解決問(wèn)題。 你經(jīng)常需要解決最短路徑問(wèn)題(shorterst-path problem)。解決最短路徑問(wèn)題的算法被稱(chēng)為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由Edward F. Moore 1959年在如何從迷宮中尋找出路這一...
摘要：再談大表示法快速排序的獨(dú)特之處在于其速度取決于選擇的基準(zhǔn)值。在平均情況下快速排序的運(yùn)行時(shí)間為在最糟情況下退化為?？焖倥判蚝秃喜⑴判虻乃惴ㄋ俣确謩e表示為和，是算法所需的固定時(shí)間量被稱(chēng)為常量。 分而治之 分而治之(divide and conquer,D&C)是一種著名的遞歸式問(wèn)題解決方法。只能解決一種問(wèn)題的算法畢竟用處有限,而D&C提供了解決問(wèn)題的思路,是另一個(gè)可供你使用的工具。 D&C...
閱讀 2174·2021-11-19 09:58
閱讀 1741·2021-11-15 11:36
閱讀 2896·2019-08-30 15:54
閱讀 3415·2019-08-29 15:07
閱讀 2790·2019-08-26 11:47
閱讀 2864·2019-08-26 10:11
閱讀 2531·2019-08-23 18:22
閱讀 2784·2019-08-23 17:58
