course4搜寻search

《course4搜寻search》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Course4搜尋Search▓Outlines本章重點Search分類觀點LinearSearchBinarySearchInterpolationSearchHashingAdvancedTreeBinarySearchTreeAVLTreeM-waySearchTreeB-treeExtendedBinaryTreeWeightedExternalPathLength(W.E.P.L)&MinimumW.E.P.L2InternalSearchv.s.ExternalSearch.StaticSearchv.s.Dyna

2、micSearch.PartialKeyv.s.WholeKeyActualKeyv.s.TransformationKey▓Search分類觀點3InternalSearchv.s.ExternalSearch觀點:資料量的多寡InternalSearch:Def:資料量少，可以一次全部置於Memory中進行search之工作ExternalSearch:Def:資料量大，無法一次全置於Memory中，須藉助輔助儲存體(E.g.Disk)，進行分段search之工作B-treeM-waySearchtree4被搜尋的資料集合

3、、資料的搜尋範圍、或資料所存在的表格，其內容是否經常異動(如:是否常做資料的插入、刪除或更新)?否:Static紙本的字典、電話簿是:Dynamic日常交易資料、電腦字典StaticSearchv.s.DynamicSearch5Def:又稱SequentialSearch。自左到右(或右到左)，逐一比較各個記錄的鍵值與搜尋鍵值是否相同。若有找到，則Found(成功搜尋);若Search完整個資料範圍仍未找到，謂之失敗(Notfound)。特質:檔案記錄不須事先排序可由RandomAccess(e.g.,Array)或Sequ

4、entialAccess(e.g.,LinkList)機制支援TimeComplexity:O(n)，n為資料個數(∵線性)▓LinearSearch(線性搜尋)6LinearSearch的演算法可分成兩種:Non-Sential(無崗哨)LinearSearchSentialLinearSearch7Non-SentialLinearSearch//記錄個數//Arrayofrecords(fileofrecords)//欲搜尋的鍵值//輸出的結果├Found:location指出記錄的所在位置└NotFound:locat

5、ion重設為042n…531Slocation8分析平均比較次數(針對“成功”的搜尋):(1+2+3+…+n)/n=n(n+1)/21/n=(n+1)/2Time:O(n)9SentialLinearSearch//記錄個數//Arrayofrecords(fileofrecords)//欲搜尋的鍵值//輸出的結果├Found:location表示出記錄的所在位置└NotFound:location為0location觀念:多一個S[0]記錄，其鍵值設定為x42n…531S0x10分析以實際的執行時間而言

6、:由於少了“測試Search範圍是否結束”之比較(即:location<=n)，所以當n極大時，大約可以省下½的比較時間。以TimeComplexity分析而言:由於仍然是線性搜尋，所以時間複雜度還是O(n)。11▓BinarySearch(二分搜尋)實施前提:檔案中記錄須事先由小到大排序過須由Random(或Direct)access之機制支援(e.g.,Array)觀念:每次皆與Search範圍的中間記錄進行比較!!while(lu)比較(k,S[m])case“=”:found,i=m,returni;case“<”:

7、u=m-1;case“>”:l=m+1;recurn0;小大lumiddleulmmS//找到了//要找的資料在左半部//要找的資料在右半部12RecursionVersion:Algorithm13IterationVersion:14分析利用TimefunctionT(n)=T(n/2)+O(1)=T(n/2)+c=(T(n/4+c))+c=T(n/4)+2c=(T(n/8)+c)+2c=T(n/8)+3c=…=T(n/n)+log2nc=T(1)+clog2n(T(1)=1,c為大於0的常數)=1+clog2nT(n

8、)=O(log2n)15▓InterpolationSearch(插補搜尋)比較符合人類Search之行為實施前提:檔案中記錄須事先由小到大排序過須由Random(或Direct)access之機制支援(e.g.,Array)作法:while(lu&&i==0)比較(x,S