續(xù)探計算復雜度搜尋問題

第八章續(xù)探計算複雜度：搜尋問題8.1僅用key的比較進行搜尋之演算法的時間複雜度下限8.1.1最差情況的下限8.1.2平均情況的下限8.2內(nèi)插搜尋8.3在樹中搜尋8.3.1二元搜尋樹(BinarySearchTree)8.3.2B-Tree8.4雜湊8.5選拔問題：AdversaryArgument序論8.5.1找出最大的key8.5.2一並找到最小與最大的key8.5.3找到次大的key8.5.4找到第k小的key8.5.5解選拔問題的或然式(Probabilistic)演算法8.1僅用key的比較進行搜尋

之演算法的時間複雜度下限8.1.1最差情況的下限定理8.18.1.2平均情況的下限分析演算法2.1平均情況的

時間複雜度(二元搜尋，遞迴版)基本運算：x與S[mid]的比較輸入大?。簄，陣列中key的數(shù)目節(jié)點距離(notedistance)：從根節(jié)點到某節(jié)點形成的路徑中含有的節(jié)點樹整體節(jié)點距離(totalnotedistance,TND)：一顆樹中所有節(jié)點距離的總和定理8.2在所有僅用key的比較，於具有n個相異key的陣列中搜尋keyx的必然式演算法中，假定x在陣列中且x出現(xiàn)在每個陣列單元的機會相等，則二元搜尋法在平均情況的效能已經(jīng)是最好的。因次在此假定下，任何這種演算法在平均情況下所做比較次數(shù)的下限近似於

8.2內(nèi)插搜尋演算法8.1

內(nèi)插搜尋(InterpolationSearch)8.3在樹中搜尋靜態(tài)搜尋：指搜尋過程中所有的紀錄一次被加到檔案中，並且之後並不會加入新的記錄或刪除紀錄動態(tài)搜尋：指搜尋過程中會頻繁的加入或刪除紀錄8.3.1二元搜尋樹(BinarySearchTree)定理8.3在所有的輸入出現(xiàn)機率相等及keyx為n個key中任一個key之機率相等的前提之下，以各種含有n個相異key的輸入建構(gòu)二元搜尋樹之平均搜尋時間近似於證明：假定要找的keyx位於搜尋樹中。8.3.2B-Trees外部搜尋：需執(zhí)行多次磁碟存取才能完成的搜尋內(nèi)部搜尋：所有的key都同時存放在記憶體中的搜尋8.4雜湊雜湊函數(shù)(hashfunction)：可將一個key對應到一個索引的函數(shù)EX：沒有任兩個key被雜湊到同一個索引的機率為定理8.4若n個key平均分佈在m個bucket中，則在一次失敗的搜尋中，進行的比較次數(shù)為n/m證明：由於這些key式平均分佈的，因此每個bucket均含有n/m個key，也就是說每個失敗的搜尋皆必須進行n/m次比較定理８.５若n個key平均分佈在m個bucket中，且每個key成為被搜尋的key的機會相等，則一次成功搜尋的平均比較次數(shù)為證明：每個bucket的平均搜尋時間等於對n/m個key進行循序搜尋的平均搜尋時間。定理8.6若n個key均勻分佈在m個bucket中，至少一個bucket含有至少k個key的機率小於等於假定一個key雜湊到任一個bucket的機會相等表8.1

8.5選拔問題：

AdversaryArgument序論8.5.1找出最大的key演算法8.2找出最大的key定理8.78.5.2一倂找到最小與最大的key演算法8.3

一並找到最小與最大的key演算法8.4

將key配對一併找出最小與最大key定理8.8任一可在各種輸入中，僅靠key的比較，就可由n個key中一併找出最小及最大key的必然式演算法，在最差情況下，必須進行至少下列數(shù)量之key的比較：8.5.3找到次大的key定理８.９僅靠key的比較，能夠在每種可能的輸入中找出次大的必然式演算法，在最差情況下，必須做至少8.5.4找到第k小的key演算法8.5選拔分析演算法8.5

平均情況的時間複雜度(選拔)基本運算：在partition副程式中的s[i]與pivotitem比較輸入大?。簄，陣列中的項目數(shù)演算法8.6利用中位數(shù)進行選拔分析演算法8.6最差情況下的

時間複雜度(利用中位數(shù)進行選拔)基本運算：在partition2中之s[i]與pivotitem的比較輸入大?。簄，陣列中的項目數(shù)最差情況時間複雜度的遞迴方程式8.5.5解選拔問題的

或然式(Probabilistic)演算法

演算法8.7

或然式選拔(Probabili