算法分析與設計
AnalysisandDesignofComputerAlgorithms
第七章時空權衡
SpaceandTimeTradeoffsaachapter時空權衡第1頁教學內(nèi)容時空權衡方法計數(shù)排序串匹配中輸入增強技術散列法B樹要求掌握時空權衡概念及基本方法，掌握時空權衡方法在常見問題中應用。算法分析與設計蘭州大學信息學院2aachapter時空權衡第2頁時空權衡時空權衡是指在算法設計中，對算法時間和空間作出權衡。通常使用額外存放空間來實現(xiàn)更加快或更方便數(shù)據(jù)存取。算法分析與設計蘭州大學信息學院3aachapter時空權衡第3頁空間換時間技術常見以空間換取時間方法輸入增強對問題部分或全部輸入做預處理,然后對得到額外信息進行存放,以加速后面問題求解。比如：計數(shù)排序，串匹配算法改進預結構存取結構—使用額外存放空間來實現(xiàn)更加快或更方便數(shù)據(jù)存取散列法，B樹動態(tài)規(guī)劃(Chapter8)動態(tài)規(guī)劃法也是與空間換時間思想相關，其基礎是把給定問題重復子問題解統(tǒng)計在表中，然后求所討論問題解。算法分析與設計蘭州大學信息學院4aachapter時空權衡第4頁注意事項時間和空間必須相互競爭？一個算法使用一個空間效率很高數(shù)據(jù)結構，這種算法又會反過來提升算法時間效率。
比如：圖遍歷-領接鏈表數(shù)據(jù)壓縮目標是節(jié)約空間而不是作為處理其它問題技術算法分析與設計蘭州大學信息學院5空間換時間技術aachapter時空權衡第5頁7.1計數(shù)排序思緒：對待排序列表中每一個元素，算出列表中小于該元素元素個數(shù)，并把結果統(tǒng)計在一張表中。顯然地，這個“個數(shù)”指出了該元素在有序列表中位置。排序時只需簡單地把列表中元素復制到它在新列表中對應位置上。算法分析與設計蘭州大學信息學院6aachapter時空權衡第6頁算法分析與設計蘭州大學信息學院7623184961947000000301100122014300501022314502193147628496待排序初始i=0i=1i=2i=3i=4i=5最終排序后7.1計數(shù)排序舉例aachapter時空權衡第7頁算法ComparisonCountingSort(A[0..n-1])//用比較計數(shù)法對數(shù)組排序//輸入：可排序數(shù)組A[0..n-1]//輸出：有序數(shù)組S[0..n-1]for(i0ton-1)Count[i]0;for(i0ton-2)for(ji+1ton-1)if(A[i]<A[j])Count[j]Count[j]+1;else Count[i]Count[i]+1;for(i0ton-1)S[Count[i]]A[i];returnS;7.1計數(shù)排序算法分析與設計蘭州大學信息學院8aachapter時空權衡第8頁算法效率實際應用時，計數(shù)排序法極少用到。不過，在一個情況下還是卓有成效，即待排序元素值都來自一個已知小集合。
比如：僅包含1，27.1計數(shù)排序算法分析與設計蘭州大學信息學院9aachapter時空權衡第9頁計數(shù)排序法一個應用是分布計數(shù)假如元素值是來自位于[l,u]之間整數(shù)，我們能夠計算出這些值出現(xiàn)頻率，然后把它們存在數(shù)組F[0..u-l]中。然后把有序列表前F[0]個位置填l，接下來F[1]個位置填入l+1.7.1計數(shù)排序算法分析與設計蘭州大學信息學院10aachapter時空權衡第10頁7.1計數(shù)排序實例：考慮下面數(shù)組排序
其中全部數(shù)字都來自于集合{11,12,13}，于是我們?nèi)ビ嬎闼鼈兂霈F(xiàn)得頻率：
接下來用這么從右到左掃描原始數(shù)組進行排序：
131112131212位置123456111212121313數(shù)組值111213頻率132分布值146分布計數(shù)排序算法分析與設計蘭州大學信息學院11aachapter時空權衡第11頁D[0]D[1]D[2]
S[0]S[1]S[2]S[3]S[4]S[5]146136126125115015121213121113A[5]=12A[4]=12A[3]=13A[2]=12A[1]=11A[0]=137.1計數(shù)排序分布計數(shù)排序算法分析與設計蘭州大學信息學院12aachapter時空權衡第12頁7.1計數(shù)排序分布計數(shù)排序算法：DistributionSort(A[0..n-1])//用分布計數(shù)法，對來自于有限范圍整數(shù)一個數(shù)組進行排序//輸入：可排序數(shù)組A[0..n-1]，其元素值位于l和u之間（l<=u）//輸出：將A中元素按照升序排列數(shù)組S[0..n-1]forj=0tou-ldoD[j]=0fori=ton-1doD[A[i]-l]=D[A[i]-l]+1forj=1tou-ldoD[j]=D[j-1]+D[j]fori=n-1to0do j=A[i]-l S[D[j]-1]=A[i] D[j]=D[j]-1returnS 算法分析與設計蘭州大學信息學院13aachapter時空權衡第13頁7.1計數(shù)排序分布計數(shù)排序
算法效率：線性效率算法
它是我們當前為止碰到過時間效率最高排序算法。
然而，分布計數(shù)排序這種高效率是因為利用了輸入列表獨特自然屬性。作為一個思索題：你是否能夠預計對于這么算法比起其它排序來講，需要多少額外空間？！算法分析與設計蘭州大學信息學院14aachapter時空權衡第14頁7.2串匹配中輸入增強技術串匹配中輸入增強思想對模式進行預處理，得到它一些信息，然后在查找過程中使用這些信息。兩種著名算法Knuth-Morris-Part(abbr.KMP)Boyer-Moore(abbr.BM)算法分析與設計蘭州大學信息學院15aachapter時空權衡第15頁7.2.1Horspool算法考慮在一些文本中查找模式BARBERs0s1...c...sn-1BARBERs0s1...S...sn-1BARBER
BARBERs0s1...B...sn-1BARBER
BARBERs0s1...MER...sn-1LEADER
LEADERs0s1...OR...sn-1REORDER
REORDER移動幅度等于模式長度移動幅度等于模式長度模式中最右邊字符c和文本中c對齊把模式中前m-1個字符中c和文本中c對齊算法分析與設計蘭州大學信息學院16aachapter時空權衡第16頁模式移動距離
對于每一個字符c，移動距離t(c)為：t(c)=模式長度m ,假如c不包含在模式前m-1個字符中模式前m-1個字符中最右邊c到模式最終一個字符距離 ,其它比如：對于模式BAEBER，E,B,R,A移動距離分別為1,2,3,4，其它為6算法ShiftTable(P[0..m-1])//用Horspool算法和Boyer-Moore算法填充移動表//輸入：模式p[0..m-1]以及一個可能出現(xiàn)字符字符表//輸出：以字母表中字符為索引數(shù)組table[0..size-1]把Table中全部元素初始化為m；for(j0tom-2)doTable[P[j]]m-1-j;returnTable;127.2.1Horspool算法算法分析與設計蘭州大學信息學院17aachapter時空權衡第17頁小結：
第一步：對于給定長度為m模式和在模式中用到字母表，按照一定描述結構字符移動表；
第二步：將模式與文本開始對齊；
第三步：重復下面過程，直到發(fā)覺了一個匹配字串或則模式抵達了文本最終一個字符以外。
第四步：從模式最終一個字符開始，比較模式和文本中對應字符，假如全部m個字符都匹配，那么匹配成功，算法停頓；不然，進入第五步；
第五步：假如碰到了一個不匹配字符，找到之前最終一個對齊字符c，然后將模式沿著文本向右移動t(c)個字符距離；
算法分析與設計蘭州大學信息學院187.2.1Horspool算法aachapter時空權衡第18頁7.2.1Horspool算法算法分析與設計蘭州大學信息學院19aachapter時空權衡第19頁Horspool算法最差效率Θ(mn)對于隨機文本，它效率為Θ(n)7.2.1Horspool算法算法分析與設計蘭州大學信息學院20aachapter時空權衡第20頁7.2.2Boyer-Moore算法假如在碰到一個不匹配字符之前，假如已經(jīng)有k(0<k<m)個字符匹配成功，則Boyer-Moore算法與Horspool算法處理不一樣。在這種情況下，Boyer-Moore算法參考兩個數(shù)值來確定移動距離。第一個數(shù)值是有文本中第一個字符c所確定，用公式t1(c)-k來計算其中t1(c)是Horspool算法用到預先算好值，k是成功匹配字符個數(shù)算法分析與設計蘭州大學信息學院21aachapter時空權衡第21頁t1(A)-2=4-2=2d1=max{t1(c)-k,1}t1(S)-2=6-2=4壞符號移動用i表示不匹配位置,i=i+patlen用i表示不匹配位置,i=i+t(‘A’)7.2.2Boyer-Moore算法算法分析與設計蘭州大學信息學院22aachapter時空權衡第22頁第二個數(shù)值是由模式中最終k>0個成功匹配字符所確定。稱為好后綴移動把模式結尾部分叫做模式長度為k后綴，記作suff(k)情況1：當模式中存在兩個以上suff(k)情況時，移動距離d2就是從第一個后綴最右元素位置數(shù)到第二個suff(k)最右邊距離。7.2.2Boyer-Moore算法算法分析與設計蘭州大學信息學院23aachapter時空權衡第23頁情況2：當模式中存在1個suff(k)情況時：k=3移動6k=3移動？次7.2.2Boyer-Moore算法算法分析與設計蘭州大學信息學院24aachapter時空權衡第24頁為了防止情況2出現(xiàn)，我們需要找出長度為l<k最長前綴，它能夠和長度一樣為l后綴完全匹配。假如存在這么前綴，我們經(jīng)過求出這么前綴和后綴之間距離來作為移動距離d2值，不然移動距離就是m7.2.2Boyer-Moore算法算法分析與設計蘭州大學信息學院25aachapter時空權衡第25頁7.2.2Boyer-Moore算法：流程圖26算法分析與設計蘭州大學信息學院aachapter時空權衡第26頁7.2.2Boyer-Moore算法算法分析與設計蘭州大學信息學院27aachapter時空權衡第27頁在一個由英文字母和空格組成文本中查找BAOBABcABCD...O...Z-t1(c)126663666壞符號移動表好后綴移動表7.2.2Boyer-Moore算法：舉例aachapter時空權衡第28頁7.3散列法散列法基本思想：把鍵分布在一個稱為散列表一維數(shù)組H[0..m-1]中。能夠利用散列函數(shù)來計算每個鍵值，該函數(shù)為每個鍵指定一個稱為散列地址值，該值是位于0到m-1之間整數(shù)。假如鍵是一個非負整數(shù)，則h(K)=Kmodm假如鍵是某個字母表中字母，則能夠把該字母在字母表中位置指定個鍵，記為ord(K)假如鍵是一個字符串c0c1...cs-1，則定義h(K)=(∑ord(ci))modm或者h0;fori0tos-1doh(h*C+ord(ci))modm算法分析與設計蘭州大學信息學院29aachapter時空權衡第29頁一個散列函數(shù)必須滿足兩個要求：需要把鍵在散列表單元中盡可能均勻分布必須是輕易計算碰撞當散列表長度m小于鍵數(shù)量n時，會有兩個或多個鍵被散列到同一個單元中即使m相對于n足夠大，碰撞還是會發(fā)生散列法兩個版本開散列（分離鏈）閉散列（開式尋址）7.3散列法算法分析與設計蘭州大學信息學院30aachapter時空權衡第30頁在開散列中，鍵被存放于散列表單元鏈表中。A,FOOL,AND,HIS,MONEY,ARE,SOON,PARTED鍵AFOOLANDHISMONEYARESOONPARTED散列地址1961071111127.3散列法-開散列/分離鏈31算法分析與設計蘭州大學信息學院aachapter時空權衡第31頁普通來說，查找效率取決于鏈表長度，而這個長度有取決于字典和散列表長度以及散列函數(shù)質量。假如該散列函數(shù)大致均勻地將n個鍵分布在散列表m個單元中，每個鏈表長度大約相當于n/m，其α=n/m稱為散列表負載因子。成功查找中平均需檢驗指針個數(shù)S=1+α/2不成功查找中平均需檢驗指針個數(shù)U=α通常情況下，我們希望負載因子和1不要相差太大。7.3散列法-開散列/分離鏈算法分析與設計蘭州大學信息學院32aachapter時空權衡第32頁全部鍵都存放在散列表本身，采取線性探查處理沖突，即碰撞發(fā)生時，假如下一個單元格空，則放下在一個單元格，假如不空，則繼續(xù)找到下一個空單元格，假如到了表尾，則返回到表首繼續(xù)。鍵AFOOLANDHISMONEYARESOONPARTED散列地址1961071111120123456789101112AFOOLAFOOLAANDFOOLHISAANDFOOLHISAANDMONEYFOOLHISAANDMONEYFOOLHISAREAANDMONEYFOOLHISARESOONPAETEDAANDMONEYFOOLHISARESOON7.3散列法-閉散列/開式尋址33算法分析與設計蘭州大學信息學院aachapter時空權衡第33頁閉散列查找和插入操作是簡單而直接，不過刪除操作則會帶來不利后果。比起分離鏈，現(xiàn)行探查數(shù)學分析是一復雜多問題。對于復雜因子為α散列表，成功查找和不成功查找必須要訪問次數(shù)分別為：S≈(1+1/(1-α))/2 U≈(1+1/(1-α)2)/2散列表規(guī)模越大，該近似值越準確7.3散列法-閉散列/開式尋址算法分析與設計蘭州大學信息學院34aachapter時空權衡第34頁
當數(shù)據(jù)膨脹到一個可怕程度時，連索引都不能被全部裝入內(nèi)存——見過印刷版EI檢索都有這個感覺，光一個檢索目錄都比我們用字典厚。處理方法就是索引再索引，顯而易見，每個索引塊都應該盡可能大，以幫助我們?nèi)〉帽M可能多信息，而防止再次查索引（此時普通都會包括外存存取）。AVL樹此時便力不從心了，我們需要一個新結構——B樹。算法分析與設計蘭州大學信息學院357.4B樹aachapter時空權衡第35頁在B樹中，全部數(shù)據(jù)統(tǒng)計都按照鍵增序存放在葉子中，它們父節(jié)點作為索引。一棵次數(shù)為m≥2B樹必須滿足下面這些結構上特征：它根要么是一個葉子，要么含有2到m個兒女；除了根和葉子節(jié)點以外每個節(jié)點，含有[m/2]到m個兒女；這個樹是（完美）平衡，即它全部葉子節(jié)點都在同一層上。7.4B樹算法分析與設計蘭州大學信息學院36aachapter時空權衡第36頁在查找鍵給定某條統(tǒng)計中，需要訪問多少個B樹節(jié)點？對于任何包含n個節(jié)點、次數(shù)為m、高度為h>0B樹來說，有：7.4B樹算法分析與設計蘭州大學信息學院37aachapter時空權衡第37頁7.4B樹B樹即平衡樹B樹索引是關系型數(shù)據(jù)庫中最為普通索引。它特點是以樹形式存放數(shù)據(jù)，不但存放了對應列數(shù)據(jù)，還存放了ROWID。索引基礎是（ROOTNODE）根節(jié)點，根節(jié)點包含指向索引下一層其它節(jié)點（分枝節(jié)點）指針，分枝節(jié)點指向索引最高/下層即葉節(jié)點。在葉節(jié)點索引項中包含了被索引列值及存放這些列值行對應（ROWID）算法分析與設計蘭州大學信息學院38aachapter時空權衡第38頁B-樹結點規(guī)模
在信息存放過程中，對于大數(shù)據(jù)庫存放，為了能確保數(shù)據(jù)高效檢索，降低IO訪問次數(shù)?，F(xiàn)有多數(shù)數(shù)據(jù)庫系統(tǒng)采取是b樹或者b+樹索引算法。
普通做法是：對于存放在物理單元上數(shù)據(jù)，進行邏輯分頁。然后緩存頁面索引。有甚至進行二次分頁。目標只有一個就是盡可能降低IO訪問。檢索時經(jīng)過對物理數(shù)據(jù)分頁，在內(nèi)存或者外存中維護關鍵字頁索引數(shù)據(jù)。當進行數(shù)據(jù)檢索時，經(jīng)過關鍵字頁匹配，把外存上物理數(shù)據(jù)讀入內(nèi)存，然后再進行匹配。對于大數(shù)據(jù)情況下，有可能需要進行屢次頁數(shù)據(jù)讀取。7.4B樹算法分析與設計蘭州大學信息學院39aachapter時空權衡第39頁
在大多數(shù)系統(tǒng)中，B-樹上算法執(zhí)行時間主要由讀、寫磁盤次數(shù)來決定，每次讀寫盡可能多信息可提升算法得執(zhí)行速度。
B-樹中結點規(guī)模普通是一個磁盤頁，而結點中所包含關鍵字及其孩子數(shù)目取決于磁盤頁大小。
注意：
①對于磁盤上一棵較大B-樹，通常每個結點擁有孩子數(shù)目(即結點度數(shù))m為50至不等
②一棵度為mB-樹稱為m階B-樹。
③選取較大結點度數(shù)可降低樹高度，以及降低查找任意關鍵字所需磁盤訪問次數(shù)。B-樹結點規(guī)模
7.4B樹算法分析與設計蘭州大學信息學院40aachapter時空權衡第40頁7.4B樹查找方法
在B-樹中查找給定關鍵字方法類似于二叉排序樹上查找。不一樣是在每個
評論
0/150
提交評論