查找技術(shù)的前世今生

查找技術(shù)的前世今生送大家兩句格言：一個人如果把從別人那里學(xué)來的東西算作自己的發(fā)現(xiàn)，這也很接近于虛驕。--黑格爾一個永遠也不欣賞別人工作的人，也就是一個永遠也不被別人欣賞的人。--汪國真講課原則1.原理上把握，貫徹數(shù)學(xué)分析

“歷史上所有偉大的思想家都在尋找一個真理，一個他人無法辯駁的真理，就像2+2=4，為了尋找這樣的真理，要實現(xiàn)這樣一個既定目標，還有什么比這個永恒而不變且不受人類情感所左右的方式更合適呢？世上除數(shù)學(xué)之外，根本不存在所謂真理，可以解答人類全部疑惑的無懈可擊的絕對真理—讓人無法反駁的論據(jù)”。

所以對于“那些數(shù)學(xué)上不可言說的，我們必須保持緘默”。 --《邏輯哲學(xué)論》第七節(jié)作者：維特根斯坦2.主流查找技術(shù),講基礎(chǔ)“墻高基下，雖得必失”--南朝宋史學(xué)家范曄算法分析的性能指標1.時間復(fù)雜度比如：遍歷一個數(shù)組的時間復(fù)雜度是O(n)2.空間復(fù)雜度內(nèi)存耗費的數(shù)量級查找查找技術(shù)與存儲（查和存）查找技術(shù)與排序都有著深刻的關(guān)系講解內(nèi)容：順序查找法折半查找法hash表法排序二叉樹平衡二叉樹堆(heap)B-樹B+樹1.順序查找法--任何程序員都會偽代碼：functionlinear_search(array,key){for(inti=0;i<array.length;i++){ if(array[i]==key){ returni; }}return-1;}科學(xué)性能指標:平均查找長度ASL（AverageSearchLength)(n+1)/2折半查找法(binarysearch)1.需要先排序快速排序（可能退化為冒泡排序法），堆排序等，時間復(fù)雜度為n*log(n)2.進行折半查找intbinary_search(intarray[],intlow,inthigh,inttarget){while(low<=high){intmid=(low+high)/2;if(array[mid]>target)high=mid-1;elseif(array[mid]<target)low=mid+1;else//findthetargetreturnmid;}//thearraydoesnotcontainthetargetreturn-1;}3.動畫/~andrzej/java/BS-applet.html二分查找法的平均查找長度當(dāng)n->無窮大的時候,極限的洛必達法則ASL=log(n+1)-1Hash表法演示動畫:http://www.cse.yorku.ca/~aaw/Hang/hash/Hash.html把一大堆元素映射到一段有限的存儲空間上。核心思想:1.存放到第幾個格子來自于key本身的信息,value只不過是個附加物2.search和insert都需要經(jīng)過關(guān)鍵的hash函數(shù)3.如果不沖突時候，時間復(fù)雜度為O(1)4.處理沖突2種方法，鏈表法，開放線性探測法注意幾點:正式的編程語言里(java,python)等，使用的是transfer法Hash表法問題：1.搬移的次數(shù)雖然不多，但也是會發(fā)生的。2.海量大數(shù)據(jù)下，比如2T數(shù)據(jù)，最壞情況下會退化為順序查找法。排序二叉樹(BinarySearchTree)BST1.概念二叉查找樹（BinarySearchTree），或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；它的左、右子樹也分別為二叉排序樹。2.動畫/~egolub/Java/BinaryTree.html3.問題如果插入的序列為隨機插入，則最壞情況下查找的時間復(fù)雜度為logn如果插入的序列為有序(無論正序還是逆序),則最壞情況下查找的時間復(fù)雜度為n,會退化為順序查找排序二叉樹的插入和刪除1.插入(insert函數(shù))分別沿路徑插入到左子樹或右子樹中2.刪除(delete/remove函數(shù))(1)若為葉子，直接刪除(2)若只有左子樹或只有右子樹，則令其孩子代替原位置(3)若左右子樹均不為空，則用直接后繼(或前驅(qū))代替其現(xiàn)有位置，再將直接后繼(或前驅(qū))刪掉。改進與優(yōu)化平衡二叉樹（AVLtree）平衡因子(BalanceFactor)概念的引入：四種可能性，平衡旋轉(zhuǎn)技術(shù)手段：LLRRRLLR平衡旋轉(zhuǎn)技術(shù)(LL)平衡旋轉(zhuǎn)技術(shù)(RR)平衡旋轉(zhuǎn)技術(shù)(LR)平衡旋轉(zhuǎn)技術(shù)(RL)最后，演示動畫http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html堆(heap)1.排序2.優(yōu)先級隊列尋路算法等用到堆的兩大性質(zhì)1.堆是一棵完全二叉樹(completebinarytree),即除了最后葉子一層的元素之外的其他層的元素包含盡可能多的元素。在最后葉子一層，所有的元素都盡可能在左邊的位置。2.堆的每個元素都大于等于孩子節(jié)點的元素。（大根堆）可以存儲在數(shù)組中堆的數(shù)組表示完全二叉樹可以用一個數(shù)組(array)表示:根節(jié)點root是array[0]非根節(jié)點array[i]的parent節(jié)點位于array[(i-1)/2]，使用integerdivision(整數(shù)除法)非根節(jié)點array[i]的左child節(jié)點位于array[2i+1],右child節(jié)點位于array[2i+2]。這個關(guān)于孩子index=2i+1或2i+2的性質(zhì)可以由等比數(shù)列求和推導(dǎo)得到堆的插入和刪除1.插入(insert)risingprocess的過程叫做reheapificationupward.2.刪除(remove/delete)removemethod刪除一個堆的元素時，我們必須刪除最大priority值的元素（優(yōu)先級隊列priorityqueue也可以由堆來實現(xiàn)，因為優(yōu)先級隊列每次拿出的是最大優(yōu)先級的元素）。如果一個堆只有一個root根元素，則直接刪除掉即可，然后減少heap的size；如果一個堆包含多于一個元素的時候，必須調(diào)整堆的結(jié)構(gòu)使其滿足堆性質(zhì)。這樣做：1.將根節(jié)點的引用copy出來。(為了這個method最后的return）2.先將葉子節(jié)點move至根節(jié)點，這樣原來那個位置上的葉子節(jié)點就被拿出來了（次被稱作out-of-placeelement）3.while（這個被move的out-of-placeelement節(jié)點小于他的孩子節(jié)點(child)){就將其最大的那個孩子與out-of-placeelement節(jié)點的位置交換。}4.returnstep1的answer源代碼intDeleteMin(){/*heap[1]istheminimumelement.Soweremoveheap[1].Sizeoftheheapisdecreased.Nowheap[1]hastobefilled.Weputthelastelementinitsplaceandseeifitfits.Ifitdoesnotfit,takeminimumelementamongbothitschildrenandreplacesparentwithit.AgainSeeifthelastelementfitsinthatplace.*//**核心思想：把堆頂?shù)膭h除，然后把完全二叉樹的最后小弟(lastElement)放到合適的位置，這里不是每次向較大的孩子交換swap的辦法向下沉淀的，而是先讓比lastElement小的元素都挪上去，騰出位置后，lastElement直接放入到那個被騰出來的合適位置。因為大的元素要往下沉，所以沒有必要每次交換2個元素（交換會費時間），只需要讓這個lastElement元素與大孩子比較，如果lastElement，直接把當(dāng)前的now賦值為他的孩子即可，而且因為把堆頂刪掉了，所以堆頂?shù)膎ow的信息丟掉而賦值他的孩子信息給他也沒什么問題。**/intminElement,lastElement,child,now;minElement=heap[1];lastElement=heap[heapSize--];//heapSize先賦值再--，這句非常精妙，表明了最后的元素不在被當(dāng)做堆中的元素了，雖然數(shù)組中仍然存在

源代碼(2)，接上頁/*nowreferstotheindexatwhichwearenow*/for(now=1;now*2<=heapSize;now=child)//注意這里的for循環(huán)每次循環(huán)體執(zhí)行結(jié)束后，是先執(zhí)行最后一個分號后的now=child,再判斷for中間的那句--是否退出循環(huán)的條件的，所以如果一般而言now最后會在循環(huán)結(jié)束后賦值為child，但是注意這里使用了break.因此直接會退出循環(huán)，而不執(zhí)行now=child{/*childistheindexoftheelementwhichisminimumamongboththechildren*//*Indexesofchildrenarei*2andi*2+1*/child=now*2;/*child!=heapSizebeacuseheap[heapSize+1]doesnotexist,whichmeansithasonlyonechild*/if(child!=heapSize&&heap[child+1]<heap[child]){child++;}/*Tocheckifthelastelementfitsotnotitsufficestocheckifthelastelementislessthantheminimumelementamongboththechildren*/if(lastElement>heap[child]){heap[now]=heap[child];}else/*Itfitsthere*/{break;//直接break出循環(huán)，now現(xiàn)在指向的就是把所有的大于lastElement挪上去后的騰出來的合適位置}}heap[now]=lastElement;returnminElement;}數(shù)學(xué)分析1.一個堆的高度為[logn]+12.推導(dǎo)堆排序

85

26

74

58

63

91

12

32

26

85

85

26

63

91

63

91

12

85

12

85

26

12

12

26

32

91

32

91

63

32

32

63

12

91

12

85

85

12

12

74

74

12

85

32

74

32

32

74

74

58

58

63

63

58

63

12

58

12

12

58

58

26

32

26

26

32

32

12

12

26

26

12

26

12動畫演示:/~jarc/idsv/lesson3.html2.百度經(jīng)典面試題問題.有海量的服務(wù)器的IP訪問日志，如何在內(nèi)存及其有限的機器(幾k的內(nèi)存，比如嵌入式設(shè)備等)上，從中找出訪問最頻繁的幾個IP？解法：時間換空間importheapqli=[random.randint(0,i)foriinxrange(1000)]#top10,還有個參數(shù)指定key，可以這樣寫key=lambdaentry:entry["count"]，在對list里每一項都是字典類型時的使用heapq.nlargest(10,li)sorted(li,reverse=True)[:10]B-樹講解前的準備（硬盤的結(jié)構(gòu)和原理）硬盤的結(jié)構(gòu)(2)硬盤的磁頭越來越接近于磁道磁頭的結(jié)構(gòu)磁盤整體結(jié)構(gòu)示意圖B-樹AB-treeofordermisanm-waytree(i.e.,atreewhereeachnodemayhaveuptomchildren)inwhich:1. thenumberofkeysineachnon-leafnodeisonelessthanthenumberofitschildrenandthesekeyspartitionthekeysinthechildreninthefashionofasearchtree（見縫插針）2. allleavesareonthesamelevel（葉子同級）3. allnon-leafnodesexcepttherootha