2020.4.1-2020.4.7 魔笛手Pied pier周记
4.1?周三?第一天
本周序言：
? ? ? ?《算法圖解》這類書是學(xué)習(xí)用書，讀起來是沒有積極性的，畢竟誰會(huì)沒事讀教材，這不是跟自己過不去嗎，但是我還必須得跟自己過不去，于是用寫博客的形式記錄下我的學(xué)習(xí)筆記。本書一共11章，每天讀一章的話11天才能讀完，一想到11天我就難受，但是要達(dá)到速戰(zhàn)速?zèng)Q，還得每天的堅(jiān)持，這個(gè)也是難得一匹，折衷想法是每天至少讀一章，長痛不如短痛。
第一章：算法簡介
（1）主要知識(shí)：二分查找，大O表示法
? ? ?1.1?二分查找：輸入要求是一個(gè)有序序列，例如經(jīng)典的猜數(shù)問題，就是根據(jù)每次將中值和要找的值進(jìn)行比對(duì)，根據(jù)大了還是小了調(diào)整查找范圍，直到查找范圍縮小到上限等于下限。對(duì)于二分查找，每次淘汰的是查找范圍一半的數(shù)值，因此就是相當(dāng)于除以2，故按照這種猜法，只需要看能被2除幾次，直到商小于1為止（淘汰的數(shù)字的至少為1嘛，小于1就是淘汰環(huán)節(jié)終止），換句話說就是查找范圍的總數(shù)等于幾個(gè)2連乘，也就是取以2為底的對(duì)數(shù)（取對(duì)數(shù)就是冪運(yùn)算的逆運(yùn)算）。
? ? ?1.2?大O表示法：O是指operator，也即操作數(shù)的次數(shù)，陳斌老師講的，也就是看的賦值語句的次數(shù)（因?yàn)橘x值語句里面同時(shí)包含表達(dá)式計(jì)算和變量存儲(chǔ)，是一個(gè)好的衡量運(yùn)行時(shí)間的標(biāo)準(zhǔn)，當(dāng)然，操作次數(shù)具體是T(n)，O()是T(n)的主導(dǎo)部分）。大O是主導(dǎo)部分的原因是因?yàn)樗撬惴ㄟ\(yùn)行時(shí)間隨著問題規(guī)模n增大時(shí)的參與貢獻(xiàn)最大的部分，也就是主要靠著它在拉動(dòng)增長，那么它就是O()的括號(hào)里面填的內(nèi)容，它甚至不需要系數(shù)，因?yàn)榧由舷禂?shù)的增長也不及隨著n的增大它本身的增大，而且它是最糟情況的下限(還有別的表示法：大歐米伽，大seita)。常見的幾種運(yùn)行時(shí)間有：對(duì)數(shù)時(shí)間（O(logn)）、線性時(shí)間O(n)，O(nlog(n))、O(n!)等。其中我們熟悉的排序算法，例如快速排序就是O(nlog(n))，選擇排序就是O()。如果能用O(n!)衡量，那么是很耗時(shí)間的算法，因?yàn)閚!的增速比還要快，所謂n的階乘，就是全排列問題，n=20時(shí)，時(shí)間消耗用你的一生衡量都太短，等結(jié)果出來了，太陽都沒了。
（2）經(jīng)典代碼
? ? 二分查找實(shí)現(xiàn)（Python）：
? ?def? binary_search(num_list,number):
? ? low=0
? ? high=len(num_list)-1
? ? while low<=high:
? ? ? ? ? ?? mid=(low+high)//2? ? ? ? ? ?#python里面地板除是//
? ? ? ? ? ? ?if num_list[mid]==number:
? ? ? ? ? ? ? ? ? ? ? ? return mid
? ? ? ? ? ? ?else if num_list[mid]<number:? ? #用中值去猜，猜的數(shù)是小了，那么我就要刷新下限，上限不變，每次只刷新一邊。
? ? ? ? ? ? ? ? ? ? ? ? low=mid+1
? ? ? ? ? ? ?else:
? ? ? ? ? ? ? ? ? ? ? ? high=mid-1
? ? return None
（3）小結(jié)感悟
? ? ? ? ? 開設(shè)“經(jīng)典代碼”模塊是因?yàn)檫^去我很抵觸這個(gè)，導(dǎo)致相關(guān)的，我就很抵觸科研，但是其實(shí)代碼寫起來很有意思，尤其是當(dāng)你慢慢地信手拈來，實(shí)現(xiàn)了一些比較酷炫的功能之后。所以，不要停止在想象的印象里，而要?jiǎng)邮植僮髌饋砀惺苤侨?#xff0c;值得一提，代碼是沒看自己寫的，一遍成功，但是只是鼓勵(lì)下，因?yàn)檫@不是什么值得高興的事，這是應(yīng)該的，在內(nèi)行看來這簡直就是1+1=2。還好這本是python版本，不然真的這本書我直接就會(huì)以語言原因不看了，那樣我會(huì)很心疼，心疼的是我的錢。說起來，數(shù)據(jù)結(jié)構(gòu)和算法和語言密切相關(guān)，因?yàn)閷?duì)同一算法的實(shí)現(xiàn)的性能不僅和算法本身相關(guān)，也和語言密切相關(guān)，當(dāng)然算法本身是本質(zhì)區(qū)別，之前看到那本紫色封面的清華出版社的嚴(yán)老師的教材，有個(gè)括號(hào)：C語言版，我當(dāng)時(shí)還覺得干嘛標(biāo)注語言，現(xiàn)在明白了，用啥實(shí)現(xiàn)也很有關(guān)系，必須要有針對(duì)性。至于為啥和語言相關(guān)，是因?yàn)楝F(xiàn)在接觸到的編程語言基本都是高級(jí)語言，都是在機(jī)器語言上的演繹，而演繹方式各有不同，導(dǎo)致操作相同的話也會(huì)有不同的運(yùn)行時(shí)間，而不像機(jī)器語言是統(tǒng)一標(biāo)準(zhǔn)的。
4.4?周六?第四天
? ? ? ?第二天就憑拖延實(shí)力說話，連續(xù)兩天都沒有看一頁，第四天了，今天一天要看三章，真的有點(diǎn)嗚嗚嗚，誰讓我懶懶兩天的，拖延的我的眼淚不值錢。（一段想要?jiǎng)澋舻幕貞?#xff0c;拖延加后悔無限循環(huán)，我什么時(shí)候有長進(jìn)5555）
第二章 ：選擇排序
（1）主要知識(shí)：數(shù)組和鏈表、選擇查找
數(shù)組和鏈表：這兩種數(shù)據(jù)結(jié)構(gòu)主要是存儲(chǔ)方式上的區(qū)別，數(shù)組是連續(xù)存儲(chǔ)，鏈表是非連續(xù)存儲(chǔ)，一個(gè)數(shù)組或者鏈表里面的元素?cái)?shù)據(jù)類型需要一致。存儲(chǔ)方式上的區(qū)別導(dǎo)致優(yōu)勢劣勢的區(qū)分：數(shù)組的元素都在一塊，相對(duì)固定，利于隨機(jī)訪問，不利于插入和刪除元素；鏈表由于非連續(xù)存儲(chǔ)，前一元素的存儲(chǔ)除了值之外還要存儲(chǔ)下一元素的地址值，在訪問方式上就只能從第一個(gè)開始訪問，是順序訪問，訪問方式上占下風(fēng)，但是由于自由散漫，因此利于插入和刪除。由于各有千秋，因此最好的方式就是各取所長的鏈表數(shù)組，數(shù)組的每一個(gè)元素都指向的是一個(gè)鏈表，這樣既可以隨機(jī)訪問，又可以隨時(shí)插入和刪除。例如facebook存儲(chǔ)用戶名，按照首字母存儲(chǔ)的鏈表數(shù)組，查找的時(shí)候首先查找首字母，再在對(duì)應(yīng)字母的鏈表里面添加。
選擇查找：就是陳斌老師講的簡單查找，第一步遍歷所有元素，找到最小元素，并轉(zhuǎn)移到新的地方，第二步遍歷剩下的元素，找到最小元素，依次類推。第一次查找次數(shù)是n,之后依次是n-1,n-2,n-3,...,1。加起來就是n(n+1)/2，忽略系數(shù)的話就是O()。我還是覺得陳老師講的方法比較能推廣，就是從程序里面分析T(n)，計(jì)算賦值語句的執(zhí)行次數(shù)，再算復(fù)雜度。
（2）經(jīng)典代碼：選擇查找（定義兩個(gè)函數(shù)，一個(gè)是找最小值，并返回下標(biāo)，另一個(gè)是依次遍歷數(shù)組，轉(zhuǎn)移）
def smallest(arr)：
smallest_num=arr[0]
smallest_index=0
for i in range(len(arr)):
? ? ? if arr[i]<smallest_num:
? ? ? ? ? ? ? ? ?smallest_num=arr[i]
? ? ? ? ? ? ? ? ?smallest_index=i
return smallest_index
def? ?choose_search(arr)：
newarr=[]
for i in range(len(arr)):
? ? ? ?smallnum=smallest(arr)
? ? ? ?newarr.append(arr.pop(smallnum))? ?
return newarr
（3）小結(jié)感悟：好的，又是一氣呵成的代碼，雖然又是特別基礎(chǔ)的。不過又有了一點(diǎn)感覺，今早躺在床上想，自己沒有用代碼實(shí)現(xiàn)的算法都不算被自己真正掌握的算法。實(shí)現(xiàn)的過程就相當(dāng)于當(dāng)老師，把這個(gè)東西吸收成自己的講給學(xué)生聽，是理論到實(shí)踐的飛躍，所以工程師是很厲害的。目前到第二章，還是沒有超過我視頻里面看到的東西，視頻講的更系統(tǒng)，更全面，更科學(xué)，但是書也是一種新思路，開闊眼界了。
第三章 ：遞歸
（1）主要知識(shí)：遞歸（遞歸條件和基線條件）、調(diào)用棧
遞歸是一種自己調(diào)用自己的函數(shù)，在函數(shù)內(nèi)部又調(diào)用自己，每調(diào)用自己一次，就縮小問題的規(guī)模一次，這就是遞歸條件，當(dāng)然參數(shù)有所變化，一層一層的轉(zhuǎn)化，直到化為可以直接返回的地步，這個(gè)地步就是基線條件。例如經(jīng)典的求階乘，就是從大數(shù)的階乘一層一層縮小到最后只有1的階乘，再從1開始返回，是一個(gè)連續(xù)的過程，既然連續(xù)，就能用到堆棧這種數(shù)據(jù)結(jié)構(gòu)去解決，call stack(調(diào)用棧)，所有函數(shù)調(diào)用都是使用堆棧實(shí)現(xiàn)的。堆棧的功能的特點(diǎn)就是連續(xù)性，可以連續(xù)插入或者彈出，例如當(dāng)前運(yùn)行函數(shù)1，函數(shù)1?的內(nèi)存區(qū)域在堆棧的最底部，函數(shù)1運(yùn)行到一部分時(shí)調(diào)用到函數(shù)2，那么函數(shù)2這時(shí)候就進(jìn)來了，如果函數(shù)2還有調(diào)用就以此類推的進(jìn)來，直到新進(jìn)來的函數(shù)可以返回，開始返回之后就會(huì)接連地彈出，直到最后函數(shù)1的彈出，程序結(jié)束。遞歸是函數(shù)調(diào)用的一種特殊情況，也就是新進(jìn)來的函數(shù)還是自己，只不過參數(shù)有所變化。最后總結(jié)，所謂堆棧，就是在執(zhí)行中調(diào)用到新的就進(jìn)來，直到新的可以開始返回，就輪到下面的舊函數(shù)執(zhí)行了。
（2）經(jīng)典代碼：求階乘
def factorial(x):
? ? ? if x==1:
? ? ? ? ? ? ? return 1
? ? ?else:
? ? ? ? ? ? ?return x*factorial(x-1)
（3）小結(jié)感悟：之前看嚴(yán)老師的書，總覺得堆棧很神秘很費(fèi)勁，單獨(dú)整一個(gè)堆棧有什么用，今天才理解原來函數(shù)調(diào)用是這樣利用堆棧的，堆棧很有用啊，基本上是基石了，害，讀書少，多見怪了，還有一個(gè)關(guān)于堆棧的就是據(jù)說黑客攻擊會(huì)從堆棧下手，這是我覺得神秘的原因。另外，還有一個(gè)點(diǎn)有被驚艷到，就是說遞歸這個(gè)思想的概念很重要，遞歸能解決的問題用循環(huán)也能解決，但是用遞歸的方式去解釋，就更直觀，尤其是某些語言沒有循環(huán)，只有將算法轉(zhuǎn)化為遞歸才可以寫，例如Haskell語言。不過其實(shí)我第一次接觸遞歸的時(shí)候我覺得很難，很抽象，想半天想不明白，不過我真的就是那種笨笨的、反應(yīng)慢，需要花時(shí)間才能理解的人，這樣想就不慌一點(diǎn)。
第四章：選擇排序
（1）主要知識(shí)：由遞歸引出的分而治之思想（DIVIDE AND CONQUER）、快速排序
分而治之思想：介紹“如何把一塊地分成若干個(gè)最大方塊的問題”，使用歐幾里得思想：適用于小塊地的最大方塊也是適用于整塊地的最大方塊。這道題的基線條件就是一塊地的長等于寬的兩倍，那么直接就可以分成兩個(gè)邊長為寬的正方形。遞歸過程是首先按照寬去分解盡可能多的方塊，再對(duì)剩下的土地執(zhí)行相應(yīng)的操作。
快速排序：指導(dǎo)思想是分而治之，每次選擇一個(gè)基準(zhǔn)值，根據(jù)基準(zhǔn)值將剩下的數(shù)分成兩個(gè)組，一個(gè)組是大于基準(zhǔn)值，另一個(gè)則相反，再對(duì)分好的兩個(gè)組執(zhí)行相同的操作，直到小組里面只剩一個(gè)值或者沒有值。注意這里基準(zhǔn)值的選取對(duì)算法復(fù)雜度有直接影響，應(yīng)該隨機(jī)選取，使得平均水平為O(nlogn)。最糟糕的水平呢，就是O()。這一講一句，還有一個(gè)合并排序（Merge sort），它的復(fù)雜度也是O(nlogn)，且一直是這個(gè)數(shù)，但是為啥還是用快速排序呢，因?yàn)閺?fù)雜度水平相同時(shí)，這個(gè)時(shí)候常量的影響力就出來了，之前我們忽略常量是因?yàn)閺?fù)雜度不可同日而語，但是一樣的時(shí)候就該比較常量了。快速排序的常量比合并排序要小，因此依然選擇看起來不穩(wěn)定但實(shí)際上更為簡潔的快速排序。
（2）經(jīng)典代碼：以數(shù)組的第一個(gè)元素為基準(zhǔn)值
def quick_sort(arr):
if len(arr)<2:
? ? ? ? ?return arr
else:
? ? ? ? ?pivot=arr[0]
? ? ? ? ?less=[for j in arr if j<pivot]
? ? ? ? ?greater=[for k?in arr if k>pivot]
? ? ? ? ?return quick_sort(less)+pivot+quick_sort(greater)
（3）小結(jié)感悟：Python真有用。（最近沒怎么讀書，思想很貧瘠，有看出來吧
4.5?第五天?周日
? ? 今天也是瘋狂趕進(jìn)度的一天。對(duì)，我又在4.6趕4.5的進(jìn)度，又在心里小聲罵昨天的自己。
第五章：散列表
（1）主要知識(shí)：散列表及其內(nèi)部機(jī)制（實(shí)現(xiàn)、沖突、散列函數(shù)
散列表：散列表的本質(zhì)是一種映射關(guān)系，類似于函數(shù)，能通過已知的自變量的值迅速得到因變量的值的一種數(shù)據(jù)結(jié)構(gòu)，在Python里面是“字典”。字典的特點(diǎn)是一個(gè)鍵對(duì)應(yīng)一個(gè)值，且鍵的數(shù)值是不能重復(fù)的。因此關(guān)于這種數(shù)據(jù)結(jié)構(gòu)就可以用來1.表征映射關(guān)系 2.需要防重復(fù)的設(shè)計(jì) 3.作為存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)（例如服務(wù)器會(huì)對(duì)常用訪問網(wǎng)頁進(jìn)行存儲(chǔ)，中央處理器中的Cache高速緩沖器，都是利用了這類數(shù)據(jù)結(jié)構(gòu)查找、插入、刪除的復(fù)雜度都是O(1)的特點(diǎn)）。散列表的內(nèi)部核心是散列函數(shù)，即利用什么樣的方式去選定存儲(chǔ)位置的索引，比如利用字符串的長度來區(qū)分、或者利用字符串的首字母來區(qū)分等等，散列函數(shù)的設(shè)計(jì)很關(guān)鍵，萬一設(shè)計(jì)不好，就會(huì)導(dǎo)致沖突，也就是說不同的鍵會(huì)分配到相同的存儲(chǔ)位置的索引，這樣也不是不行，這樣的話一個(gè)位置當(dāng)然放不下，就會(huì)生成一個(gè)鏈表，這個(gè)索引的位置就是存儲(chǔ)的鏈表，本來查找就是一對(duì)一比較快，這樣的話找到位置了還要面對(duì)一個(gè)鏈表進(jìn)行二次選擇，那就違背我的初衷遼，因此呢，我的散列函數(shù)的設(shè)計(jì)就是要1.分散 2.均勻（再品一品“散列”兩個(gè)字，是不是覺得這個(gè)名字完全就是濃縮的精華），也沒有完美的散列函數(shù)，面對(duì)紛繁復(fù)雜的數(shù)據(jù)都能做到分散均勻的，總是不免出現(xiàn)一個(gè)多個(gè)鍵影射到一個(gè)位置或者分布相對(duì)較滿的情況，于是呢，需要調(diào)整，一旦被填充的部分占所有位置的比例超過百分之七十，那么就需要resize數(shù)組空間，然后將原來的鍵映射到新的寬敞的數(shù)組空間中來，降低這個(gè)填充比例。即使有這樣一個(gè)resize的過程，使用散列表這種數(shù)據(jù)結(jié)構(gòu)去存儲(chǔ)查找的速度依然比數(shù)組去存儲(chǔ)要快很多，當(dāng)然是在平均情況下啦。
（2）經(jīng)典代碼：使用字典作為投票檢查器和使用字典作為服務(wù)器緩存
1.book={}
def one_vote(name):
? ? ? if book[name]:
? ? ? ? ? ? ? ? print('Go home and come back to your mother')
? ? ? ?else:
? ? ? ? ? ? ?book[name]=True
? ? ? ? ? ? ?print('You can vote now')
2.cache={}
def storage(url):
? ? ? ? if cache.get(url):
? ? ? ? ? ? ? ? return cache[url]
? ? ? ? else:
? ? ? ? ? ? ? cache[url]=get_data_from_server(url)? ? ? ? ? #從服務(wù)器中找到這個(gè)url對(duì)應(yīng)的網(wǎng)址并存儲(chǔ)在cache中
? ? ? ? ? ? ? return cache[url]
（3）小結(jié)感悟：雖然Python編程語言很高級(jí)，很多東西都封裝好了，幾乎沒有底層的東西，很好上手，這樣看好像不需要了解內(nèi)部機(jī)制是什么樣的，但是了解底層才對(duì)這個(gè)東西的掌握程度更好，就像買一件衣服，你還知道這衣服的面料以及加工過程，那么你在穿的時(shí)候就更能選擇a more proper occasion.(沉迷這種體了，騷瑞)，學(xué)習(xí)底層的東西很有必要，俺的個(gè)人看法。
第六章：廣度優(yōu)先搜索
（1）主要知識(shí)：數(shù)據(jù)結(jié)構(gòu)圖（有向圖和無向圖）、廣度優(yōu)先搜索（查找最短路徑）、隊(duì)列（先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)）
廣度有限搜索用于解決最短路徑，其使用的主要方法是圖算法。所謂圖，由節(jié)點(diǎn)（node）和邊（edge）組成，節(jié)點(diǎn)之間由邊連接起來，邊分為單向和雙向，單向則為有向圖，雙向則為無向圖。對(duì)于要求最短路徑的目標(biāo)，我們先轉(zhuǎn)化為“有路徑嗎”的問題。先看從起點(diǎn)開始，一步能到達(dá)的地方，再看兩步能到達(dá)的地方，以此類推，我們的終點(diǎn)出現(xiàn)在三步能到達(dá)的地方，因此，三步就是最短路徑，這就是核心思想，朋友里面沒有你要找的人，那么再看朋友的朋友里面有沒有你要找的人，注意找的時(shí)候不要出現(xiàn)重復(fù)查找的情況，也就是你的朋友和你朋友的朋友是同一個(gè)人的情況，這樣不僅效率低下，而且還可能出現(xiàn)死循環(huán)的情況。如何實(shí)現(xiàn)先從朋友里面找，再在朋友的朋友里面找的順序呢？采用隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。隊(duì)列和對(duì)堆棧正好相反，是先進(jìn)先出（First in First Out），保證了能夠按照添加順序進(jìn)行檢查。另外，使用字典實(shí)現(xiàn)”朋友的朋友“這種對(duì)應(yīng)關(guān)系。
（2）經(jīng)典代碼：
from collection import deque
graph={} #利用字典建立對(duì)應(yīng)關(guān)系
graph['you']=['Alice','Bob','Claire']
graph['Bob']=['anuj','peggy']? ?#此處僅添加這兩個(gè)?不作一一列舉
def search(name):
? ? ??search_sequence=deque()#建立隊(duì)列實(shí)現(xiàn)按照添加順序查找
? ? ? search_sequence+=graph[name]
? ? ? searched=[]
? ? ? while search_queue:
? ? ? ? ? ? ? person=search_queue.popleft()
? ? ? ? ? ? ? if person not in searched:
? ? ? ? ? ? ? ? ? ? ? ? if person_is_seller(person):
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?print person+'is a mango seller'
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?return True
? ? ? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? search_quene+=graph[person]? #這個(gè)人不是芒果商?于是把這個(gè)人的朋友加入隊(duì)列進(jìn)行檢查
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? searched.append(name) #記錄已經(jīng)檢查過的不是芒果商的人
? ? ? ? return False #如果到這里說明找完了朋友，也找完了朋友的朋友，朋友的朋友的朋友等等，沒找到，所以就沒有芒果商
search('you')
（3）小結(jié)感悟：不同的數(shù)據(jù)結(jié)構(gòu)有他適應(yīng)的問題，分析問題所需，選擇對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，另外，有一個(gè)小技巧，是防止重復(fù)的，可以新建一個(gè)列表，用于記錄已經(jīng)操作過的數(shù)字，在每次操作之前判斷一下是in還是not in就可以。
4.10?周五（我太懶了?我接受了?不掙扎了?我看我不配有被要求 哼！！！氣人?開頭的十一天真的一點(diǎn)都不長哦！甚至太短了！
第七章：狄克斯特拉算法
（1）主要知識(shí)：廣度優(yōu)先搜索找出的是段數(shù)最少的路徑，對(duì)象是沒有加權(quán)的圖。狄克斯特拉算法對(duì)象是有向無環(huán)加權(quán)圖(注意與無向圖實(shí)際上就是有環(huán)圖，因?yàn)闊o向圖就是兩個(gè)節(jié)點(diǎn)之間互相相連，另外狄克斯特拉算法僅針對(duì)的是權(quán)重為正的，也就是“單增性”，總結(jié)下為有向加權(quán)圖，對(duì)于負(fù)權(quán)圖，應(yīng)采用Bellman-Ford算法)。列一張表，對(duì)當(dāng)前沒有被更新過的最便宜的開銷節(jié)點(diǎn)，計(jì)算當(dāng)前點(diǎn)到終點(diǎn)的最近距離從而更新有關(guān)系的節(jié)點(diǎn)，如果最終不僅想計(jì)算最小開銷，還想知道最短路徑，只需要再在表格里面加一列“父節(jié)點(diǎn)‘即可，也即每次更新的時(shí)候順便將對(duì)應(yīng)的父節(jié)點(diǎn)記錄下來。最終順著終點(diǎn)-終點(diǎn)的父節(jié)點(diǎn)-父節(jié)點(diǎn)的父節(jié)點(diǎn)這樣的順序回溯回去就能得到最短路徑。
（2）經(jīng)典代碼：
2.1 數(shù)據(jù)結(jié)構(gòu)準(zhǔn)備：三個(gè)字典和一個(gè)列表，分別存儲(chǔ)有向加權(quán)圖、開銷表、父節(jié)點(diǎn)表以及處理過的節(jié)點(diǎn)。第一，graph['節(jié)點(diǎn)A'][’節(jié)點(diǎn)A的下一節(jié)點(diǎn)‘]=’權(quán)重值‘，graph['節(jié)點(diǎn)']本身就是一個(gè)字典，所以這是一個(gè)二級(jí)字典，是字典的字典，可以通過graph['A'].keys()訪問和節(jié)點(diǎn)A相連的所有節(jié)點(diǎn)。開銷表和父節(jié)點(diǎn)表就是兩個(gè)一級(jí)字典，鍵值就是所有節(jié)點(diǎn)。處理過的節(jié)點(diǎn)列表為processed。另外，無窮大在python里面表示為float('inf')
2.2 主函數(shù)和子函數(shù)
主函數(shù)：node=find_lowest_cost_node(cost) #最初選取最便宜的節(jié)點(diǎn)，且最便宜的節(jié)點(diǎn)沒有被處理過
? ? ? ? ? ? ? while node is not None:
? ? ? ? ? ? ? ? ? ? ? ? ? cost=cost[node]
? ? ? ? ? ? ? ? ? ? ? ? ? neighbors=graph[node]
? ? ? ? ? ? ? ? ? ? ? ? ? for n in neighbors.keys():
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if neighbor[node]+cost<cost[n]:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cost[n]=neighbor[node]+cost
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? father[n]=node
? ? ? ? ? ? ? ? ? ? ? ? ? ?processed.append(node)
? ? ? ? ? ? ? ? ? ? ? ? ? ?node=find_lowest_cost_node(cost)
子函數(shù)：def find_lowest_cost_node(cost):
? ? ? ? ? ? ? ? ? ? ? ? low_cost=float('inf')
? ? ? ? ? ? ? ? ? ? ? ? low_cost_node=None
? ? ? ? ? ? ? ? ? ? ? ? for n in cost and not in processed:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?cost=cost[n]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cost<low_cost:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? low_cost=cost
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? low_cost_node=n
? ? ? ? ? ? ? ? ? ? ? ? ?return low_cost_node
（3）小結(jié)感悟：算法原理和實(shí)際實(shí)現(xiàn)之間有一定的距離，這個(gè)距離就是數(shù)據(jù)結(jié)構(gòu)的準(zhǔn)備。所以在實(shí)現(xiàn)算法的時(shí)候，首先整理好合適的數(shù)據(jù)結(jié)構(gòu)，再動(dòng)手寫代碼。狄克斯特拉狄克斯特拉狄克斯特拉，我真的記不住這個(gè)名字。
第八章：貪婪算法
（1）主要知識(shí)：所謂NP完全問題，就是無法在有限時(shí)間內(nèi)完成的事情。算法復(fù)雜度在指數(shù)級(jí)別甚至階乘級(jí)別的，其時(shí)間消耗隨著問題規(guī)模的增長是爆炸式的，是在有生之年無法解決的，例如本書中列舉的集合覆蓋問題和旅行商問題，集合覆蓋問題需要列出所有集合組合的情況，組合數(shù)相加的和是2的階乘；旅行商問題是將要去的地方進(jìn)行排列，我們知道全排列是n的階乘。人生苦短，既然找到全局最優(yōu)解是不可能滴，那么我們在有限時(shí)間內(nèi)找到接近全局最優(yōu)解的局部最優(yōu)解也是好的，不求完美，優(yōu)秀也是極好的。貪婪算法就是一種近似算法，是試圖以局部最優(yōu)解去代替全局最優(yōu)解的算法。貪婪算法的主要思想是每次都找當(dāng)前最優(yōu)的做法，以背包問題為例的話就是每次都拿剩下的物品中最值錢的東西。
（2）經(jīng)典代碼：以集合覆蓋問題為例，每次都覆蓋剩下區(qū)域最多的廣播臺(tái)為best station，直到不剩下區(qū)域需要覆蓋
while states_need:
? ? ? ? best_station=None
? ? ? ? state_covered=set()? ? ?#初始化最大重疊區(qū)域
? ? ? ? for state,station in station.items():? ?#遍歷廣播站，找到和當(dāng)前剩下區(qū)域重疊最大的廣播站
? ? ? ? ? ? ? ? ? ?cover=state_needed&station
? ? ? ? ? ? ? ? ? ?if len(cover)>len(state_covered):? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?best_station=state
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?state_covered=cover? #一旦找到最大重疊的就賦值給它
? ? ? ? ?state_needed-=state_needed
? ? ? ? final_station.append(best_station)
（3）小結(jié)感悟：處理問題的時(shí)候先看看是不是NP完全問題，如果是的話就可以用貪婪算法。
第九章：動(dòng)態(tài)規(guī)劃
(1)主要知識(shí)：動(dòng)態(tài)規(guī)劃（找有限制條件下的最優(yōu)解）的基本思想和遞歸是一樣的，都是將大問題轉(zhuǎn)化為子問題來解決，找到每步的遞推式，因此能用動(dòng)態(tài)規(guī)劃的一般也都能用遞歸解決。動(dòng)態(tài)規(guī)劃是自底向上的解決方法，遞歸是自頂向下的解決方法。在具體實(shí)現(xiàn)上，動(dòng)態(tài)規(guī)劃多是列表問題，有的是一維列表，有的是二維列表，具體看限制條件。例如經(jīng)典的背包問題，就是二維列表，總?cè)萘肯拗茷?磅，那么我們就從1磅開始看，1磅最多能裝多少價(jià)值的，然后2磅，3磅依次填下去。表格的橫軸是磅數(shù)，縱軸就是各種物品，一行一行地填，每新加1磅，就看能不能放下當(dāng)前行的物品，如果可以的話計(jì)算總價(jià)值=當(dāng)前物品價(jià)值+剩余磅數(shù)的價(jià)值（這個(gè)之前就算出來了，在表格里面有），不可以的話就直接照抄左邊的值，這就是遞推式。關(guān)于為啥從1磅開始，因?yàn)樽钚〉奈锲肪褪侵?磅，按照這個(gè)最小物品的重量去定顆粒度。另外，動(dòng)態(tài)規(guī)劃的經(jīng)典應(yīng)用還有“最長公共子序列”和“最長公共子串‘的問題，也都是二維列表，橫軸縱軸當(dāng)然就是需要比較的兩個(gè)字串了。”最長公共子序列’的遞推式就是當(dāng)前的橫軸縱軸對(duì)應(yīng)的字母是否相同，相同的話就由左上角的對(duì)角格的數(shù)加一，否則就是0；“最長公共子串”的遞推式也是同樣的判斷，如果相同的話也是一樣計(jì)算，不相同的話就照抄左邊格子和上邊格子中的大的值。
(2)經(jīng)典代碼：代碼沒有什么好講的，主要就是幾個(gè)if判斷，二位列表的計(jì)算等。
(3)小結(jié)感悟：這類算法還是需要多刷題，難點(diǎn)在于識(shí)別這類問題和找出遞推式，另外注意遞推式的初始值是需要自己找的。
第十章：K近鄰算法
（1）主要知識(shí)：K近鄰是一種分類或者回歸算法，而分類問題就是分組問題，回歸問題就是預(yù)測值問題。怎么分組和預(yù)測值呢？首先將分類對(duì)象特征化，對(duì)每個(gè)對(duì)象進(jìn)行“編號(hào)‘，使用這個(gè)編號(hào)去代表它，所以這個(gè)特征是否具有代表性就很大程度地決定算法性能。再計(jì)算編號(hào)之間的”距離’或者“夾角‘來判斷是否相似。和誰相似自然就是和誰一組，到這里分組已經(jīng)解決，預(yù)測值的話就是把和他相近的這幾個(gè)人的值處理一番后得到新的值就大功告成了。所謂K近鄰就是分組或者預(yù)測值的時(shí)候，找?guī)讉€(gè)人來參考。找5個(gè)人就是5近鄰。推薦系統(tǒng)就有利用K近鄰的原理去做，首先計(jì)算相似度，找到最相似的K個(gè)人，通過這K個(gè)人的數(shù)據(jù)去給這個(gè)人推薦電影或者預(yù)測這個(gè)人對(duì)某部電影的打分。
（2）經(jīng)典代碼：重在思想，沒有列代碼，在python里面也應(yīng)該主要是調(diào)包了，scipy/sklean等。
（3）小結(jié)感悟：這本書很厲害的一點(diǎn)就是把枯燥的算法講的深入淺出，看起來很高端的算法被他講的好像也很好理解和上手。
第十一章：算法進(jìn)階
（1）主要知識(shí)：對(duì)基礎(chǔ)算法有簡單了解之后，本書作者繼續(xù)介紹了更加深入的10類算法。
1.樹：之前介紹的二分法查找是需要對(duì)有序列表進(jìn)行查找，那么二叉搜索樹（左小右大）就是一種適應(yīng)這種算法的數(shù)據(jù)結(jié)構(gòu)，但是二叉搜索樹可能存在不平衡（一邊特別長）的問題，所以就還有紅黑樹、B樹、堆和伸展樹。
2.反向索引：主要是搜索方面的應(yīng)用，例如建立搜索關(guān)鍵詞為鍵值、網(wǎng)頁為值的字典，這種是為服務(wù)用戶的反向索引。
3.傅里葉變換：BetterExplained這么解釋傅里葉變換：如果你給他一杯沙冰，他能給你分析出有什么成分。
4.并行算法：將任務(wù)分解為一個(gè)個(gè)子任務(wù)，子任務(wù)不同的處理器中運(yùn)行，最終再將結(jié)果合并。
5.Mapreduce:是一種需要很多處理器的分布式算法，可以在短時(shí)間內(nèi)處理海量工作。其中map是映射函數(shù)，可以對(duì)列表中的每一個(gè)數(shù)做相同的操作，reduce是歸并函數(shù)，也就是將列表中的所有數(shù)進(jìn)行某個(gè)迭代式的運(yùn)算，最終輸出一個(gè)值。
6.布隆過濾器和Hyperloglog：當(dāng)準(zhǔn)確查找需要很大的工作量的時(shí)候，可以使用這樣一種算法：結(jié)果不保證完全正確，但是大概率是準(zhǔn)確的，可能出現(xiàn)錯(cuò)報(bào)，但是不可能出現(xiàn)漏報(bào)。以判定網(wǎng)站是否被搜集為例，如果返回”這個(gè)網(wǎng)頁已經(jīng)被搜集’，那么也很可能沒有被搜集；但是如果返回“這個(gè)王爺沒有被搜集”，那么這網(wǎng)頁就是一定沒有被搜集。
7.SHA算法：回顧一下之前學(xué)的散列函數(shù)（哈希函數(shù)），就是將數(shù)據(jù)映射到存儲(chǔ)空間的某個(gè)位置的函數(shù)，那么這個(gè)SHA呢，就是secure hash algorithm，安全哈希函數(shù)。同樣是映射，這個(gè)算法可以將對(duì)象映射到一個(gè)字符串，而且這個(gè)字符串不能倒推回原始對(duì)象，也就是說可以用來加密，也可以用來比對(duì)較大的文件，計(jì)算他們的哈希值并比較即可，節(jié)約時(shí)間。另外就是可以存儲(chǔ)用戶密碼，存儲(chǔ)密碼的哈希值即可，每次輸入密碼，計(jì)算哈希值并和數(shù)據(jù)庫里面的哈希值進(jìn)行比對(duì)。
8.局部敏感的哈希算法：之前介紹的哈希算法對(duì)輸入對(duì)象相差不大的情況是沒有顯現(xiàn)的，也就是說即使是相差不大的兩個(gè)東西，那么他們的哈希值也可能是大不相同的，局部敏感的哈希算法就是解決了這類問題，將這一特征體現(xiàn)在哈希值上，改進(jìn)為局部敏感的，當(dāng)輸入差不多的時(shí)候，那么他們的哈希值也是相差不大的，便于在相似情況下的比對(duì)。
9.diffie-hellman密鑰交換：雙方不需要知道加密算法，不需要協(xié)調(diào)要使用的加密算法，而且非常難以破解。DH算法使用公鑰和密鑰，公鑰是公開的，發(fā)件人使用公鑰進(jìn)行加密，收件人使用私鑰進(jìn)行解密。
10.線性規(guī)劃：線性規(guī)劃是作者知道的最酷的算法之一，他是在給定條件下最大限度地改善指定的指標(biāo)的算法。所有的圖算法都可以用線性規(guī)劃來解決。
（2）小結(jié)感悟：學(xué)海無涯。
總結(jié)
以上是生活随笔為你收集整理的2020.4.1-2020.4.7 魔笛手Pied pier周记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
