国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

查找算法——JS算法實(shí)現(xiàn)

cheng10 / 842人閱讀

摘要：查找表查找表相關(guān)概念查找表是由同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合。由于集合中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。缺點(diǎn)平均查找長度較大。索引順序表的查找若以索引順序表表示靜態(tài)查找表，則查找可以用分塊查找。

查找表 search table 查找表相關(guān)概念

查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于"集合"中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。

靜態(tài)查找表 static search table

動(dòng)態(tài)查找表 dynamic search table

關(guān)鍵字 key 關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。

靜態(tài)查找表 順序表的查找

順序查找的過程：從表中的最后一個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字與給定的值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功。

小技巧：監(jiān)視哨 在查找表的第一個(gè)記錄中存儲(chǔ)在要查找的值，則可以避免查找過程中每一步都要檢測(cè)整個(gè)表是否查找完畢。
優(yōu)點(diǎn)
算法簡單且適應(yīng)面廣，對(duì)表的結(jié)構(gòu)無任何要求。
缺點(diǎn)
平均查找長度較大。特別是當(dāng)n很大時(shí)，查找效率較低，為(1+n)/2。

有序表的查找

折半查找
先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。

折半查找的效率比順序查找高，但折半查找只適用于有序表，且限于順序存儲(chǔ)結(jié)構(gòu)(對(duì)線性鏈表無法有效地進(jìn)行折半查找)

斐波那契查找

F0 =0，
F1=1;
Fi=F(i-1)+F(i-2);

斐波那契查找的平均性能優(yōu)于折半查找，但是最壞情況下的性能卻比折半查找差。O（logn），它還有一個(gè)優(yōu)點(diǎn)就是分割時(shí)只進(jìn)行加，減運(yùn)算。

插值查找
插值查找是根據(jù)給定值key來確定進(jìn)行比較的關(guān)鍵字的查找方法。

令i=(key-ST[l].key)(h-l+1)/(ST[h].key-ST[l].key)。
其中ST[l].key和ST[h].key分別為有序表中具有最小關(guān)鍵字和最大關(guān)鍵字的記錄。顯然這種插值查找只適于關(guān)鍵字分布均勻的表，在這種情況下，對(duì)表長較大的順序表，其平均性能比折半查找好。

靜態(tài)樹表的查找

前面對(duì)有序表的查找性能的討論是在“等概率”的前提下進(jìn)行的。但有序表中各個(gè)記錄的查找概率不等式，則可以采用靜態(tài)樹表的查找。

如果只考慮查找成功的情況，則使查找性能達(dá)到最佳的判定樹是其帶權(quán)內(nèi)路徑長度之和PH值取最小的二叉樹(靜態(tài)最優(yōu)查找樹 static optimal search table)。
由于構(gòu)建靜態(tài)最優(yōu)查找樹花費(fèi)的時(shí)間代價(jià)較高，因此僅介紹一種構(gòu)造近似最優(yōu)查找樹(nearly optimal search table)的有效算法。

索引順序表的查找

若以索引順序表表示靜態(tài)查找表，則查找可以用分塊查找。
分塊查找又稱為索引順序查找，這是順序查找的一種改進(jìn)方法。在這種查找方法中，除表本身外，還需要建立一個(gè)“索引表”。將所有記錄劃分成多個(gè)子表，對(duì)每個(gè)子表建立一個(gè)索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)(保存該子表內(nèi)的最大關(guān)鍵字)和指針項(xiàng)(指示該子表的第一個(gè)記錄在表中的位置)。

動(dòng)態(tài)查找表

動(dòng)態(tài)查找表的特點(diǎn)是，表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成的，即對(duì)于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。

二叉排序樹 binary sort tree

定義

若左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值(關(guān)鍵字)都小于根結(jié)點(diǎn)的值；

若右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值(關(guān)鍵字)都大于根結(jié)點(diǎn)的值；

左、右子樹都分別是二叉排序樹。

結(jié)論：若按中序遍歷一棵二叉排序樹，所得到的結(jié)點(diǎn)序列是一個(gè)遞增序列。

平衡二叉樹 AVL balanced binary tree

定義
它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。

紅黑樹

AVL

B-和B+樹

留

鍵樹(數(shù)字查找樹)

留

哈希表 哈希表的構(gòu)造方法

直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。若其中H(key）中已經(jīng)有值了，就往下一個(gè)找，直到H(key）中沒有值了，就放進(jìn)去。

數(shù)字分析法：分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時(shí)我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會(huì)很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會(huì)明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。

平方取中法：當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。

折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對(duì)齊，然后相加；間界疊加是從一端向另一端沿分割界來回折疊，然后對(duì)齊相加。

隨機(jī)數(shù)法：選擇一隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)值作為散列地址，通常用于關(guān)鍵字長度不同的場合。

除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對(duì)p的選擇很重要，一般取素?cái)?shù)或m，若p選的不好，容易產(chǎn)生同義詞。

處理沖突的方法

開放定址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）為散列函數(shù)，m為散列表長，di為增量序列，可有下列三種取法：
1.1. di=1,2,3，…，m-1，稱線性探測(cè)再散列；

1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）稱二次探測(cè)再散列；
1.3. di=偽隨機(jī)數(shù)序列，稱偽隨機(jī)探測(cè)再散列。

再哈希法：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)散列函數(shù)地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間。

鏈地址法（拉鏈法）將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中

建立一個(gè)公共溢出區(qū)，一旦沖突全部填入溢出表

參考資料

動(dòng)態(tài)查找--二叉排序樹

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/107000.html

相關(guān)文章

  • 查找算法——JS算法實(shí)現(xiàn)

    摘要：查找表查找表相關(guān)概念查找表是由同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合。由于集合中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。缺點(diǎn)平均查找長度較大。索引順序表的查找若以索引順序表表示靜態(tài)查找表，則查找可以用分塊查找。 查找表 search table 查找表相關(guān)概念 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于集合中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因...

    sihai 評(píng)論0 收藏0

  • 【二分查找】| 模擬 20 萬數(shù)據(jù)快速查詢 IP 歸屬地

    摘要：通過兩個(gè)二分查找的條件繼續(xù)進(jìn)行問題的分析，那么問題又來了，二分查找是快速的查找一個(gè)數(shù)據(jù)是否存在一組數(shù)據(jù)中，而且效率極高，億查找一個(gè)數(shù)據(jù)只需次查找。二分查找的三點(diǎn)重點(diǎn)循環(huán)退出條件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);這篇文章主要深入數(shù)據(jù)結(jié)構(gòu)與算法在解決實(shí)際問題怎么運(yùn)用和分析的，對(duì)于 IP...

    The question 評(píng)論0 收藏0

  • 2016年前端開發(fā)學(xué)習(xí)計(jì)劃

    摘要：年，軟件開發(fā)界發(fā)生了很多變化。六數(shù)據(jù)存儲(chǔ)是一個(gè)關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，由瑞典公司開發(fā)，目前屬于旗下公司。最流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，在應(yīng)用方面是最好的，關(guān)系數(shù)據(jù)庫管理系統(tǒng)應(yīng)用軟件之一。七是最新的修訂版本，年月由萬維網(wǎng)聯(lián)盟完成標(biāo)準(zhǔn)制定。 2015年，軟件開發(fā)界發(fā)生了很多變化。有很多流行的新語言發(fā)布了，也有很多重要的框架和工具發(fā)布了新版本。下面有一個(gè)我們覺得最重要的簡短清單，同時(shí)也有我們覺...

    asoren 評(píng)論0 收藏0

  • 2016年前端開發(fā)學(xué)習(xí)計(jì)劃

    摘要：年，軟件開發(fā)界發(fā)生了很多變化。六數(shù)據(jù)存儲(chǔ)是一個(gè)關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，由瑞典公司開發(fā)，目前屬于旗下公司。最流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，在應(yīng)用方面是最好的，關(guān)系數(shù)據(jù)庫管理系統(tǒng)應(yīng)用軟件之一。七是最新的修訂版本，年月由萬維網(wǎng)聯(lián)盟完成標(biāo)準(zhǔn)制定。 2015年，軟件開發(fā)界發(fā)生了很多變化。有很多流行的新語言發(fā)布了，也有很多重要的框架和工具發(fā)布了新版本。下面有一個(gè)我們覺得最重要的簡短清單，同時(shí)也有我們覺...

    Null 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<