大一下-數(shù)算sessdsa-05sort search數(shù)據(jù)結(jié)構(gòu)與算法Python05排序搜索

據(jù) 〉本章目據(jù)結(jié)與 〉順序搜與算（ 〉二分搜（〉）〉 地球與空間科學(xué)學(xué)院 本章目 〉了 據(jù)構(gòu) 〉了 構(gòu)算法 算法 〉）〉了解抽象數(shù)據(jù)類型：映射）〉地球與空間科學(xué)學(xué)院 順序搜索Sequential構(gòu)算數(shù)〉如果數(shù)據(jù)項(xiàng)保存在如列表這樣的集合中，我們會(huì)稱這些數(shù)據(jù)項(xiàng)具有 線性或者順序關(guān)系，在PythonList中，這些數(shù)據(jù)項(xiàng)的位置稱 以按照順序來和查找數(shù)據(jù)項(xiàng)，這種技術(shù)就稱為“順序搜索”構(gòu)算法 要確定列表中是否存在需要查找的數(shù)據(jù)項(xiàng)，首先從列表的第1個(gè)數(shù)項(xiàng)開始，按照下標(biāo)增長的順序，逐個(gè)比對(duì)數(shù)據(jù)項(xiàng)，如果到最后一 都未發(fā)現(xiàn)要查找的項(xiàng)，那么搜索失敗地球與空間科學(xué)學(xué)院 順序搜索：無序表搜索代（）地球與空間科學(xué)學(xué)院 順序搜索構(gòu)數(shù) 〉 要對(duì)搜索算法進(jìn)行分析，首先要確定其中的基本計(jì)算步?；仡櫟趽?jù) 二章算法分析的要點(diǎn)，這種基本計(jì)算步驟必須要足夠簡單，并且在結(jié) 構(gòu)與法 在搜索算法中，這種基本計(jì)算步驟就是進(jìn)行數(shù)據(jù)項(xiàng)的比法 在順序搜索算法中，為了保證是討論的一般情形，需要假定列表 的數(shù)據(jù)項(xiàng)并沒有按值排列順序，而是隨機(jī)放置在列表中的各個(gè) 數(shù)據(jù)項(xiàng)是否在列表中，比對(duì)次數(shù)是不一樣最好的情況，第1次比對(duì)就找到 的情況，要n次比地球與空間科學(xué)學(xué)院 順序搜索 數(shù)據(jù)項(xiàng)在列表中，比對(duì)的一般情形如何結(jié) 結(jié) 所以平均狀況下，比對(duì)的次數(shù)是 所以，順序搜索的算法復(fù)雜度是BestBestWorstAverageitemis1nitemisnotnnn）〉 這里我們假定列表中的數(shù)據(jù)項(xiàng)是無序的，那么如果數(shù)據(jù)項(xiàng)排了序，順序搜索算法的效率又如何呢？地球與空間科學(xué)學(xué)院 順序搜索 實(shí)際上，我們在第三章的有序表Search方法實(shí)現(xiàn)中介紹過順序搜結(jié) 結(jié)與 與 ?如下圖中搜索數(shù)據(jù)項(xiàng)50，當(dāng)看到54時(shí)，可知道后面不可能（ 在50，可以提前退出搜（）地球與空間科學(xué)學(xué)院 順序搜索：有序表搜索代（ 地球與空間科學(xué)學(xué)院 順序搜索 順序搜索有序表的各種情況分BestWorstAverageBestWorstAverageitemis1nitemisnot1n（ 實(shí)際上，就算法復(fù)雜度而言，仍然是） 只是在數(shù)據(jù)項(xiàng)不存在的時(shí)候，有序表的搜索能節(jié)省一些比對(duì)次數(shù)但并不改變其數(shù)量地球與空間科學(xué)學(xué)院 二分搜數(shù)〉那么對(duì)于有序表，有沒有更好的搜索算據(jù)與法結(jié)〉在順序搜索中，如果第1個(gè)數(shù)據(jù)項(xiàng)不匹配查找項(xiàng)的話，那最多還有n- 與法（ 我們從列表中間開始比對(duì)）列表中 查 ，那么查找項(xiàng)只可能出 半部列表中 查 ，那么查找項(xiàng)只可能出現(xiàn)在后半部 繼續(xù)采用上面的方法搜地球與空間科學(xué)學(xué)院 二分搜索：代（中 ）學(xué)院 地學(xué)院 二分搜索：分而治之（Divide& 二分搜索算法實(shí)際上體現(xiàn)了解決問題的另一個(gè)典型策略：分而治結(jié) 結(jié)與 與算 顯然，遞歸算法就是一種典型的分而治之策略，二分法也適合用 歸算法來 地球與空間科學(xué)學(xué)院 二分搜索 由于二分搜索每次比對(duì)都將下一步的比對(duì)范圍縮小一半，每次比ApproximateNumberofItemsApproximateNumberofItems123i（） 當(dāng)比對(duì)次數(shù)足夠多以后，比對(duì)范圍內(nèi)就會(huì)僅剩余1個(gè)數(shù)據(jù)項(xiàng)，無論個(gè)數(shù)據(jù)項(xiàng)是否匹配查找項(xiàng)，比對(duì)最終都會(huì)結(jié)束，解下列方程 所以二分法搜索的算法復(fù)雜度是O(log地球與空間科學(xué)學(xué)院 二分搜索：進(jìn)一步的考 雖然我們根據(jù)比對(duì)的次數(shù)，得出二分搜索的復(fù)雜度O(logn)，但 注意到本算法中除了比對(duì)，還有一個(gè)因素需要注意到 與 這個(gè)遞歸調(diào)用使用了列表切片，而切片操作的復(fù)雜度是O(k)，這樣會(huì)使與 法 ） 〉 另外，雖然二分搜索在時(shí)間復(fù)雜度上優(yōu)于順序搜索，但也要考慮對(duì)數(shù)據(jù) 行排序的開銷〉 所以，在算法選擇的問題上，光看時(shí)間復(fù)雜度的優(yōu)劣是不夠的，需要考慮到實(shí)際應(yīng)用的情況。地球與空間科學(xué)學(xué)院 前面我們利用數(shù)據(jù)集中關(guān)于數(shù)據(jù)項(xiàng)之間排列關(guān)系的知識(shí)，來將搜 算 算法 現(xiàn)在我們進(jìn)一步來構(gòu)造一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，能使得搜索算法的復(fù)度降到O(1)，這種概念稱為“散列） 〉 能夠使得搜索的次數(shù)降低常數(shù)級(jí)別，我們對(duì)數(shù)據(jù)項(xiàng)所處的位置就必須有 的先驗(yàn)知識(shí)。如果我們事先能知道要找的數(shù)據(jù)項(xiàng)應(yīng)該出現(xiàn)在數(shù)據(jù)集中的什么位置，就可以直接到那個(gè)位置看看數(shù)據(jù)項(xiàng)是否。 由數(shù)據(jù)項(xiàng)的值來確定其存放位置，如何能做到這一點(diǎn)呢地球與空間科學(xué)學(xué)院 散列：基本概 散列表（hashtable，又稱哈希表）是一種數(shù)據(jù)集，其中數(shù)據(jù)項(xiàng)構(gòu)據(jù) 方式尤其有利于將來快速的搜索定位。散列表中的每一個(gè)結(jié) 位置，稱為槽（slot），有一個(gè)稱。與構(gòu)法 例如：一個(gè)包含11個(gè)槽的散列表，槽的名稱分別為法（ 在插入數(shù)據(jù)項(xiàng)之前，每個(gè)槽的值都是None，表示空 實(shí)現(xiàn)從數(shù)據(jù)項(xiàng) 〉 下面例子，散列函接受數(shù)據(jù)項(xiàng)作為參數(shù)，返回整數(shù)值0～10項(xiàng) 的號(hào)地球與空間科學(xué)學(xué)院 散列：示 為了將數(shù)據(jù)項(xiàng)保存到散列表中，我們設(shè)計(jì)第一個(gè)散列函結(jié) 數(shù)據(jù)項(xiàng)結(jié)構(gòu) 有一種常用的散列方法是“求余數(shù)”，將數(shù)據(jù)項(xiàng)除以散列表的大小法 得到的余數(shù)作為槽號(hào)法 實(shí)際上“求余數(shù)” ）Hash45609 本例中我們的散Hash45609地球與空間科學(xué)學(xué)院 散列：示構(gòu)數(shù)〉按照散列函數(shù)h(item)，為每個(gè)數(shù)據(jù)項(xiàng)計(jì)算出存放的位置之后，就 構(gòu)算 算法 數(shù)據(jù)項(xiàng)都保存到散列表后，搜索就變得無比簡單，要查找某個(gè)數(shù)項(xiàng)是否存在于表中，我們只需要使用同一個(gè)散列函數(shù)，對(duì)查 行計(jì)算，測試下返回的槽號(hào)所對(duì)應(yīng)的槽中是否有數(shù)據(jù)項(xiàng)〉 不，你可能也看出這個(gè)方案的問題所，這組數(shù)據(jù)相當(dāng)湊巧，自占據(jù)了不同的槽，假如還要保存44，h(44)=，它跟77被分配到同一個(gè)0#槽中，這種情況稱為“ collison”，我們后面會(huì)討的決方案。完美散列函數(shù)：PerfectHash 給定一組數(shù)據(jù)項(xiàng)，如果一個(gè)散列函數(shù)能把每個(gè)數(shù)據(jù)項(xiàng)映射到不同 槽中，那么這個(gè)散列函數(shù)就可以稱為“完美散列函數(shù)構(gòu) 構(gòu)與 但如果數(shù)據(jù)項(xiàng)經(jīng)常性的變動(dòng)，很難有一個(gè)系統(tǒng)性的方法來設(shè)計(jì)對(duì)（ 的完美散列函數(shù)（當(dāng)然 假如我們要保 號(hào)（11位數(shù)字），完美散列函數(shù)得要求散列表具有 退而求其次的話，好的散列函數(shù)需要具備3個(gè)特性 最少（近完美）、計(jì)算難度低（額外開銷?。⒊浞址稚?shù)據(jù)項(xiàng)（節(jié)約空間地球與空間科學(xué)學(xué)院 折疊法設(shè)計(jì)散列函數(shù)的基本步驟是，將數(shù)據(jù)項(xiàng)按照位數(shù)分為若干段 再將幾段數(shù)字相加，最后對(duì)散列表大小求余，得到散列 例如， ，可以兩位兩位分為4段（62、76、72法 55），相加（62+76+72+55=265），散列表包括11個(gè)槽，那么就法 265%11=1，所以 有時(shí)候折疊法還會(huì)包括一個(gè)隔數(shù)反轉(zhuǎn)的步驟，比如（62、76、72 55）隔數(shù)反轉(zhuǎn)為（62、67、72、55），再累加（62+67+72+55=256），對(duì)11求余（256%11=3），所以 雖然隔數(shù)反轉(zhuǎn)從理論上看來毫無必要，但這個(gè)步驟確實(shí)為折疊法到散列函數(shù)提供了一種微 ，以便更好符合上述的3個(gè)特性地球與空間科學(xué)學(xué)院 平方取中法，首先將數(shù)據(jù)項(xiàng)做平方運(yùn)算，然后取平方數(shù)的中間兩位 再對(duì)散列表的大小求結(jié)與 例如，對(duì)44進(jìn)行散列，首先44*44=1936，然后取中間的93，對(duì)散與法 表大小11求余法（Mid-34759 Mid-34759）6地球與空間科學(xué)學(xué)院 散列函數(shù)設(shè)計(jì)：非數(shù) 我們也可以對(duì)非數(shù)字的數(shù)據(jù)項(xiàng)（如字符串）進(jìn)行散列，把字符串 的每個(gè)字符看作ASCII碼整數(shù)即結(jié) 如cat，ord('c')==99,ord('a')==96, 再將這些整數(shù)累加，對(duì)散列表大小求（）地球與空間科學(xué)學(xué)院 散列函數(shù)設(shè) 當(dāng)然，這樣的散列函數(shù)對(duì)所有的變位詞都返回相同的散列值，為 防止這一點(diǎn)，可以將字符串所在的位置作為權(quán)重因子，乘以ord結(jié)與 我們還可以設(shè)計(jì) 的散列函數(shù)方法，但要堅(jiān)持的一個(gè)基本出與法 點(diǎn)是，散列函數(shù)不能稱 過程和搜索過程的計(jì)算負(fù)擔(dān)，如果法 列函數(shù)設(shè)計(jì)太過復(fù)雜，去花費(fèi)大量的計(jì)算資源計(jì)算槽號(hào)，可能還如簡單地進(jìn)行順序搜索或者二分搜索，失去了散列本身的意）地球與空間科學(xué)學(xué)院 解決方 如果兩個(gè)數(shù)據(jù)項(xiàng)被散列映射到同一個(gè)槽，需要有一個(gè)系統(tǒng)化的方 在散列表中保存第二個(gè)數(shù)據(jù)項(xiàng)，這個(gè)過程稱為“解 ”結(jié)與 前面提到，如果說散列函數(shù)是完美的，那就不會(huì)有散 ，但與法 美散列函數(shù)常常是不現(xiàn)實(shí)的，所以解決散 成為散列方法中法 重要的一部 解決散列 法就是 的數(shù)據(jù)項(xiàng)再找一個(gè)開放的空槽來 存，其中最簡單的就是 的槽開始往后掃描，直到碰到一個(gè)槽。（如果到散列表的尾部還未找到，則要從首部接著掃描 這種尋找空槽的技術(shù)稱為“開放定址openaddressing”，向后個(gè)槽尋找的方法則是開放定址技術(shù)中的“線性探測linear地球與空間科學(xué)學(xué)院 解決方案：線性探測Linear 接前例，我們把44、55、20逐個(gè)插入到散列表中結(jié) 結(jié) h(55)==0，同樣0#槽已經(jīng)被占據(jù)，向后找到第一個(gè)空槽2#，保與 法（ 采用線性探測方法來解決散 的話，則散列表的查找也遵循樣的規(guī) 找項(xiàng)，或者碰到空槽（搜索失敗）大解決方案：線性探測的改構(gòu)數(shù)〉線性探測法的一個(gè)缺點(diǎn)是有（clustering）的趨勢，即如果同 一個(gè)槽的數(shù)據(jù)項(xiàng)較多的話，這些數(shù)據(jù)項(xiàng)就會(huì)在槽附近起來， 構(gòu)與（ 避 法就是將線性探測擴(kuò)展，從逐個(gè)探測改為跳躍探地球與空間科學(xué)學(xué)院 解決方案：再散列 重新尋找空槽的過程可以用一個(gè)更為通用的“再散列 來概括，也就是說newhashvalue=結(jié) 對(duì)于線性探測來說，rehash(pos)=(pos+1)%與 “+3”的跳躍式探測則是：rehash(pos)=(pos+3)%法 跳躍式探測的再散列通式是：rehash(pos(pos+skip 跳躍式探測中，需要注意的是skip的取值，不能被散列表大小整除 否則會(huì)產(chǎn)生周期，造成很多空