18總結(jié)課數(shù)據(jù)結(jié)構(gòu)編程語句基礎(chǔ)算法體現(xiàn)了哪些數(shù)學(xué)思想

2019-01-23 進(jìn)入課之前的17講，我們從小處著眼，介紹了離散數(shù)學(xué)中最常用的一些知識點(diǎn)。我講到了很多數(shù)據(jù)結(jié)構(gòu)、編程語句和基礎(chǔ)性算法。這些知識點(diǎn)看似是孤立的，但是內(nèi)部其實(shí)有很多聯(lián)系。今我們從最簡單的數(shù)據(jù)結(jié)構(gòu)數(shù)組開始說。自從你開始接觸計(jì)算機(jī)編程，數(shù)組一定是你經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)。它的特點(diǎn)你應(yīng)該很清楚。數(shù)組可以通過下標(biāo)，直接定位到所需的數(shù)據(jù)，因此數(shù)組特別適合快速地隨機(jī)訪問。它常常和循環(huán)語句相結(jié)合，來實(shí)現(xiàn)迭代法，例如二分查找、斐波那契數(shù)列等等。另外，我們將要在“線性代數(shù)篇”介紹的矩陣，也可以使用多維數(shù)組來表示。不過，數(shù)組只對稠密的數(shù)列更有效。如果數(shù)列非常稀疏，那么很多數(shù)組的元素就是無效值，浪費(fèi)了存儲(chǔ)空間。此外，數(shù)組中元素的插入和刪除也比較麻煩，需要進(jìn)行數(shù)據(jù)的批量移動(dòng)。數(shù)據(jù)，而鏈表結(jié)點(diǎn)之間的相連關(guān)系，在C和C++語言中是通過指針來實(shí)現(xiàn)的，而在Java鏈表的特點(diǎn)是不能通過下標(biāo)來直接訪問數(shù)據(jù)，而是必須按照存儲(chǔ)的結(jié)構(gòu)逐個(gè)讀取。這樣做的優(yōu)勢在于，不必事先規(guī)定數(shù)據(jù)的數(shù)量，也不再需要保存無效的值，表示稀疏的數(shù)列時(shí)可以更有效的利用存儲(chǔ)空間，同時(shí)也利于數(shù)據(jù)的動(dòng)態(tài)插入和刪除。但是，相對于數(shù)組而言，鏈表無法支持快速地隨機(jī)訪問，進(jìn)行讀寫操作時(shí)就更耗時(shí)。和數(shù)組一樣，鏈表也可以是多維的。對于非常稀疏的矩陣，也可以用多維鏈表的結(jié)構(gòu)來表達(dá)。此外，在鏈表結(jié)構(gòu)中，點(diǎn)和點(diǎn)之間的連接，分別體現(xiàn)了圖論中的頂點(diǎn)和邊。因此，我們還可以使用指針、對象引用等來表示圖結(jié)構(gòu)中的頂點(diǎn)和邊。常見的圖模型，例如多叉樹、無向圖和有向圖等，都可以用指針或引用來實(shí)現(xiàn)。在數(shù)組和鏈表這些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)之上，我們可以構(gòu)建更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，比如哈希表、隊(duì)列和棧等等。這些數(shù)據(jù)結(jié)構(gòu)，提供了邏輯更復(fù)雜的模型，可以通過數(shù)組、鏈表或兩者的結(jié)合來實(shí)現(xiàn)。第2中，哈希表的實(shí)現(xiàn)采用的是鏈地址哈希表。這種方法的主要思想是，先分配一個(gè)很大的數(shù)組空間，而數(shù)組中的每一個(gè)元素都是一個(gè)鏈表的頭部。隨后，我們就可以根據(jù)哈希函數(shù)算出的哈希值（也叫哈希的ey），找到數(shù)組的某個(gè)元素及對應(yīng)的鏈表，然后把數(shù)據(jù)添加到這個(gè)鏈表中。每個(gè)元素對應(yīng)了一個(gè)鏈表，那么當(dāng)發(fā)生沖突的時(shí)候，我們就可以把多個(gè)數(shù)據(jù)添加到同一個(gè)鏈表中?？墒牵讯鄠€(gè)數(shù)據(jù)存放在一個(gè)鏈表，就代表訪問效率不高。所以，我們要盡量找到一個(gè)合理的哈希函數(shù)，減少?zèng)_突發(fā)生的機(jī)會(huì)，提升檢索的效率。2我們把對100求余作為哈希函數(shù)。因此數(shù)組的長度是100。對于每一個(gè)數(shù)字，通過它對100求余，確定它在數(shù)組中的位置。如果多個(gè)數(shù)字的求余結(jié)果一樣，就產(chǎn)生沖突，使用鏈表來解決。我們可以看到，表中位置98的鏈表沒有沖突，而0、1、2、3和99位置的鏈說完了哈希，我們來看看棧這種數(shù)據(jù)結(jié)構(gòu)。我在介紹樹的深度優(yōu)先搜索時(shí)講到棧。它是先進(jìn)后出的。在我們進(jìn)行函數(shù)遞歸的時(shí)候，函數(shù)調(diào)用和返回的順序，也是先進(jìn)后出，所以，棧體現(xiàn)了遞歸的思想，可以實(shí)現(xiàn)基于遞歸的編程。實(shí)際上，計(jì)算機(jī)系統(tǒng)里的函數(shù)遞歸，在內(nèi)部也是通過棧來實(shí)現(xiàn)的。雖然直接通過棧來實(shí)現(xiàn)遞歸不如函數(shù)遞歸調(diào)用那么直觀，但是，由于?？梢员苊膺^多的中間變量，它可以節(jié)省內(nèi)存空間的使用。我在介紹廣度優(yōu)先搜索策略時(shí)，談到了隊(duì)列。隊(duì)列和棧最大的不同在于，它是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，先進(jìn)入隊(duì)列的元素會(huì)優(yōu)先得到處理。隊(duì)列模擬了日常生活中人們排隊(duì)的現(xiàn)象，其思想已經(jīng)延伸到很多大型的數(shù)據(jù)系統(tǒng)中，例如消息隊(duì)列。在消息系統(tǒng)中，生產(chǎn)者會(huì)源源不斷地推送新的數(shù)據(jù)，而消費(fèi)者會(huì)對這些消息進(jìn)行處理?？墒?，有時(shí)消費(fèi)者的處理速度會(huì)慢于生產(chǎn)者推送的速度，這會(huì)帶來很多復(fù)雜的后續(xù)問題，因此我們可以通過隊(duì)列實(shí)現(xiàn)消息的緩沖。新產(chǎn)生的數(shù)據(jù)會(huì)先進(jìn)入隊(duì)列，直到消費(fèi)者處理它。經(jīng)過這樣的異步處理，消息的隊(duì)列實(shí)現(xiàn)了生產(chǎn)者和消費(fèi)者的松耦合，對消費(fèi)者起到了保護(hù)作用，使它不容易被數(shù)據(jù)洪流沖垮。比哈希表，隊(duì)列和棧更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)是基于圖論中的各種模型，例如各種二叉樹、多叉樹、有向圖和無向圖等等。通常，這些模型表示了頂點(diǎn)和頂點(diǎn)之間的稀疏關(guān)系，所以它們常常是基于指針或者對象引用來實(shí)現(xiàn)的。我在講前綴樹、社交關(guān)系圖和交通地圖的案例中，都使用了這些模型。另外，樹模型中的多叉樹、特別是二叉樹體現(xiàn)了遞歸的思想。之前的遞歸編程的案例中的圖示也可以對應(yīng)到多叉樹的表示。條件語句的一個(gè)關(guān)鍵元素是布爾表達(dá)式。它其實(shí)體現(xiàn)了邏輯代數(shù)中邏輯和集合的概念。邏輯代數(shù)，也被稱為布爾代數(shù)，主要包括了邏輯表達(dá)式及其相關(guān)的邏輯運(yùn)算，可以幫助我們消除自然語言所帶來的歧義，并嚴(yán)格、準(zhǔn)確地描述事物。在編程語言中，我們把邏輯表達(dá)式和控制語言結(jié)合起來，比如Jaa語言的f語句：復(fù)制代碼1if(表達(dá)式){函數(shù)體1}else{函數(shù)體2}：若表達(dá)式為真，執(zhí)行函數(shù)體1，否則執(zhí)行函數(shù)體2當(dāng)然，邏輯代數(shù)在計(jì)算機(jī)中的應(yīng)用，遠(yuǎn)不止條件語句。例如SQL語言中的elect語句和布爾檢索模型。elect是SL查詢語言中十分常用的語句。這個(gè)語句將根據(jù)指定的邏輯表達(dá)式，在一個(gè)數(shù)據(jù)庫中進(jìn)行查詢并返回結(jié)果，而返回的結(jié)果就是滿足條件的記錄之集合。類似地，布爾檢索模型利用邏輯表達(dá)式，確定哪些文檔滿足檢索的條件并把它們作為結(jié)果返回。如，SQL語言中的Join操作。Join內(nèi)連接（innerjoin）：假設(shè)被連接的兩張數(shù)據(jù)表分別是左表和右表，那么內(nèi)連接查詢能據(jù)。如果認(rèn)為左表是集合A，右表是集合B，那么從集合的角度來說，內(nèi)連接產(chǎn)生的結(jié)果是A、B兩個(gè)集合的交集。外連接（outerjoin）：外連接可以保留左表，右表或全部表。根據(jù)這些行為的不同，可循環(huán)語句可以讓我們進(jìn)行有規(guī)律性的重復(fù)性操作，直到滿足某個(gè)條件。這和迭代法中反復(fù)修改某個(gè)值的操作非常一致。所以循環(huán)常用于迭代法的實(shí)現(xiàn)，例如二分或者牛頓法求解方程的根。在之前的迭代法講解中，我經(jīng)常使用循環(huán)來實(shí)現(xiàn)編碼。另外，循環(huán)語句也會(huì)經(jīng)常和布爾表達(dá)式相結(jié)合。嵌套的多層循環(huán)，常常用于比較多個(gè)元素的大小，或者計(jì)算多個(gè)元素之間的相似度等等，這也體現(xiàn)了排列組合的思想。介紹分治思想的時(shí)候，我談及了MapReduce的數(shù)據(jù)切分。在分布式系統(tǒng)中，除了數(shù)據(jù)切它并不關(guān)心每臺(tái)服務(wù)器當(dāng)前的負(fù)載。如果我們對每個(gè)請求標(biāo)上一個(gè)自動(dòng)增加的ID，我們可以認(rèn)為輪詢算法是對請求的ID進(jìn)行求余操作（或者是求余的哈希函數(shù)），被除數(shù)就是可用服務(wù)器的數(shù)量，余數(shù)就是接受請求的服務(wù)器ID。而源地址哈希進(jìn)一步擴(kuò)展了這個(gè)思想，擴(kuò)它可以對請求的IP或其他唯一標(biāo)識進(jìn)行哈希，而不一定是請求的不管是對何種數(shù)據(jù)進(jìn)行哈希變換，也不管是何種哈希函數(shù)，只要能為每個(gè)請求確定哈希另外，在第9節(jié)中，我談到了字符串的編輯距離，但是沒有涉及字符串匹配的算法。知名的RK（Rabin-Karp）匹配算法，在暴力匹配（BruteForce）基礎(chǔ)之上，充分利用了迭代首先，RK算法可以根據(jù)兩個(gè)字符串哈希后的值。來判斷它們是不是相同。如果哈希值不同，則兩個(gè)字符串肯定不同，不用再比較；此外，RK算法中的哈希設(shè)計(jì)非常巧妙，讓相鄰兩個(gè)子字符串的哈希值產(chǎn)生了固定的聯(lián)系，讓我們可以通過前一個(gè)子串的哈希值，推導(dǎo)出后一個(gè)子串的哈希值，這樣就能使用迭代法來計(jì)算每個(gè)子串的哈希值，大大減少了用于哈希函數(shù)的計(jì)算。八皇后和0/1背包等等。回溯實(shí)際上體現(xiàn)了遞歸和排列的思想。不過，它對搜索空間做了在前兩節(jié)講述算法復(fù)雜度分析的時(shí)候，我已經(jīng)從數(shù)學(xué)的角度出發(fā)，總結(jié)了幾個(gè)常用的法則，包括四則運(yùn)算、主次分明、齊頭并進(jìn)、排列組合、一圖千言和時(shí)空互換。這些法則體現(xiàn)了數(shù)學(xué)中的運(yùn)算優(yōu)先級、數(shù)量級、多元變量、圖論等思想。這些我們上兩節(jié)剛剛講過，我就不多說了，你可以參考之前的內(nèi)容快速復(fù)習(xí)一下。從數(shù)據(jù)結(jié)構(gòu)的角度來看，最基本的數(shù)組遍歷體現(xiàn)了迭代的思想，而鏈表和樹的結(jié)構(gòu)可用于刻畫圖論中的模型。棧的先進(jìn)后出、以及隊(duì)列的先進(jìn)先出，分別適用于圖的深度優(yōu)先和廣度優(yōu)先遍歷。哈希表則充分利用了哈希函數(shù)的特點(diǎn)，大幅降低了查詢的時(shí)間復(fù)雜度。當(dāng)然，僅僅使用數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)還不夠，我們還需要操作這些數(shù)據(jù)。為了實(shí)現(xiàn)操作的流程，條件語句使用了布爾代數(shù)來控制編程邏輯，循環(huán)和函數(shù)嵌套使用迭代、遞歸和排列組合等思想來實(shí)現(xiàn)更精細(xì)的數(shù)學(xué)模型。但是，有時(shí)候我們面對的問題太復(fù)雜了，除了數(shù)據(jù)結(jié)構(gòu)和基本的編程語句，我們還需要發(fā)明一些算法。為了提升算法的效率，我們需要對其進(jìn)行復(fù)雜度分析。通常，這些算法中的數(shù)學(xué)思想就更為明顯，因?yàn)樗鼈兌际菫榱私鉀Q特定的問題，根據(jù)特定的數(shù)學(xué)模型而設(shè)計(jì)的。有的時(shí)候，某個(gè)算法會(huì)體現(xiàn)多種數(shù)學(xué)思想，例如RK字符串匹配算法，同時(shí)使用了迭代法和哈希。此外，多種數(shù)學(xué)思維可能都是相通的。比如，遞歸的思想、排列的結(jié)果、二進(jìn)