各種查找算法性能比較測試(順序查找、二分查找)

1、算法設(shè)計與分析各種查找算法的性能測試目錄摘要4第一章：簡介（Introduction）51.1 算法背景5第二章：算法定義（Algorithm Specification）52.1 數(shù)據(jù)結(jié)構(gòu)52.2順序查找法的偽代碼62.3 二分查找（遞歸）法的偽代碼62.4 二分查找（非遞歸）法的偽代碼7第三章：測試結(jié)果（Testing Results）93.1 測試案例表93.2 散點圖10第四章：分析和討論124.1 順序查找124.1.1 基本原理124.2.2 時間復(fù)雜度分析124.2.3優(yōu)缺點124.2.4該進(jìn)的方法134.2 二分查找（遞歸與非遞歸）134.2.1 基本原理134.2.2 時間復(fù)

2、雜度分析144.2.3優(yōu)缺點144.2.4 改進(jìn)的方法14附錄：源代碼（基于C語言的）16聲明18摘要在計算機許多應(yīng)用領(lǐng)域中，查找操作都是十分重要的研究技術(shù)。查找效率的好壞直接影響應(yīng)用軟件的性能，而查找算法又分靜態(tài)查找和動態(tài)查找。我們設(shè)置待查找表的元素為整數(shù)，用不同的測試數(shù)據(jù)做測試比較，長度取固定的三種，對象由隨機數(shù)生成，無需人工干預(yù)來選擇或者輸入數(shù)據(jù)。比較的指標(biāo)為關(guān)鍵字的查找次數(shù)。經(jīng)過比較可以看到，當(dāng)規(guī)模不斷增加時，各種算法之間的差別是很大的。這三種查找方法中，順序查找是一次從序列開始從頭到尾逐個檢查，是最簡單的查找方法，但比較次數(shù)最多，雖說二分查找的效率比順序查找高，但二分查找只適用于有序

3、表，且限于順序存儲結(jié)構(gòu)。關(guān)鍵字：順序查找、二分查找（遞歸與非遞歸）第一章：簡介（Introduction） 1.1 算法背景 查找問題就是在給定的集合（或者是多重集，它允許多個元素具有相同的值）中找尋一個給定的值，我們稱之為查找鍵。 對于查找問題來說，沒有一種算法在任何情況下是都是最優(yōu)的。有些算法速度比其他算法快，但是需要較多的存儲空間；有些算法速度非?？?，但僅適用于有序數(shù)組。查找問題沒有穩(wěn)定性的問題，但會發(fā)生其他的問題（動態(tài)查找表）。 在數(shù)據(jù)結(jié)構(gòu)課程中，我們已經(jīng)學(xué)過了幾種查找算法，比較有代表性的有順序查找（蠻力查找），二分查找 （采用分治技術(shù)），哈希查找（理論上來講是最好的查找方法）。 第二

4、章：算法定義（Algorithm Specification）2.1 數(shù)據(jù)結(jié)構(gòu)三種查找都是以整形數(shù)組作為主要的數(shù)據(jù)結(jié)構(gòu)，如Int an。我們主要測試的是算法的性能，并不是僅僅對算法的查找，以數(shù)組作為主要的數(shù)據(jù)結(jié)構(gòu)能滿足實驗的要求。2.2順序查找法的偽代碼 算法：順序查找法目的：在給定的集合（或者是多重集，允許多個元素具有相同的值）中找尋一個給定的值。前提：給定一給定一個集合（或多重集）（A1、A2、A3、A4.An）。返回：尋找出給定值。偽代碼如下： int SeqSearch1(int r , int n, int k) /數(shù)組r1 rn存放查找集合，n是數(shù)組中元素的個數(shù)（即查找表的長度），

5、k是要查找的元素 i=n;/從后往前把表中的元素與要查找的元素進(jìn)行比較 while (i0 & ri!=k) i-; return i;/i的值為0則沒找到，為非0則i為要查找元素的位置 2.3 二分查找（遞歸）法的偽代碼 算法：二分查找（遞歸）法 目的：在給定的集合（或者是多重集，允許多個元素具有相同的值）中找尋一個給定的值。 前提：給定一給定一個集合（或多重集）（A1、A2、A3、A4.An）。 返回：尋找出給定值。 偽代碼如下：int search(int a,int n,int k)/查找表放在數(shù)組a中，n是查找表中元素的個數(shù)，k是待查找的元素 Low=0,High=n-1;/選擇查找

6、的最大的范圍 Mid=(Low+High)/2; if (Low=High)|(n=-1) return -1;/數(shù)字-1表示沒有結(jié)果else if (aMid=k) return Mid; /找到要查找的元素 else if (aMidg) return (search(a,Mid-1,g);/需要在左邊的更小的范圍內(nèi)查找 elsereturn (search(a+Mid+1,n-Mid,g);/在右邊的更大的范圍內(nèi)查找 2.4 二分查找（非遞歸）法的偽代碼 算法：二分查找（非遞歸）法目的：在給定的集合（或者是多重集，允許多個元素具有相同的值）中找尋一個給定的值。前提：給定一給定一個集合（或

7、多重集）（A1、A2、A3、A4.An）。返回：尋找出給定值。偽代碼如下：int BinarySearch(int a,int n,int k) /查找表放在數(shù)組a中，n是查找表中元素的個數(shù)，k是待查找的元素。 Low=0; high=n-1; /置區(qū)間初值while(lowai) low=middle+1;/在后半?yún)^(qū)間查找 elsehigh=middle-1;/在前半?yún)^(qū)間查找 return 0;/查找失敗第三章：測試結(jié)果（Testing Results）3.1 測試案例表實驗項目二 各種查找算法的性能測試（數(shù)據(jù)數(shù)多少不同時用時）數(shù)據(jù)N排序3080200200010000順序查找0000.00

8、150.002二分查找（遞歸）00000.001二分查找（非遞歸）00000實驗項目二 各種查找算法的性能測試（查找值不同時用時）數(shù)據(jù)K排序10251204775000順序查找00000二分查找（遞歸）00000二分查找（非遞歸）000003.2 散點圖 在測試過程中n的值取了30、80、200、2000、10000；取這些值是因為我想測試在隨機數(shù)多少不一的情況下所用時間的區(qū)別。經(jīng)過實驗發(fā)現(xiàn)查找過程中三種查找方法都很迅速，但當(dāng)數(shù)字增大時還是有些差別，順序查找用時最多。 在實驗過程中我們在同規(guī)模5000的情況下把key值取了10、25、120、477、5000；取這些值是想看看在查找值不一的情況

9、下所用時間的不同。經(jīng)過實驗發(fā)現(xiàn)無論key取值多少三種查找時間依舊相同。 實驗中我們所預(yù)期的結(jié)果是：輸入不同的規(guī)模，根據(jù)隨機數(shù)的產(chǎn)生，三種查找方法都會出現(xiàn)相應(yīng)的時間?？墒?，實驗過程中，隨機數(shù)的原因，很多次測量都是0，就只有極少數(shù)的情況下會出現(xiàn)時間，而且出現(xiàn)的時間都很小，都是0.001或者0.002。第四章：分析和討論4.1 順序查找4.1.1 基本原理 從表的一端向另一端逐個進(jìn)行記錄的關(guān)鍵字和給定值（要查找的元素）的比較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查找記錄；反之，若直至第一個記錄，其關(guān)鍵字和給定值比較都不等，則表明表中沒有所查記錄，查找不成功。4.2.2 時間復(fù)雜度分

10、析 由于順序查找是從表的一端向另一端逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較，對于n個元素的表，不成功的比較次數(shù)為n，查找成功：最好的情況為1次，最差的情況為n次，所以查找成功時的平均查找長度為(n+1)/2，且順序查找的時間復(fù)雜度為O(n)。4.2.3優(yōu)缺點 與其他查找算法相比，其缺點是平均查找長度較大，特別是當(dāng)n較大時，查找效率低，但他有個很大的優(yōu)點是算法簡單且適應(yīng)面廣，它對表的結(jié)構(gòu)無任何要求，無論記錄是否按關(guān)鍵字有序均可應(yīng)用。4.2.4該進(jìn)的方法4.2 二分查找（遞歸與非遞歸）4.2.1 基本原理二分查找又稱折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中間的那個元素，則

11、找到要查找的元素，查找成功；如果要查找的元素比中間的那個元素小則使用相同的策略只在左邊的區(qū)間查找就可以；如果要查找的元素比中間的那個元素大，則使用相同的策略在右邊的區(qū)間進(jìn)行查找；每次將待查找的元素的所在區(qū)間縮小一半。4.2.2 時間復(fù)雜度分析 二分查找的時間復(fù)雜度是O(log(n)，最好的情況是指針mid指的第一個數(shù)就是要找的值，最壞的情況的所找的值是第一個或最后一個數(shù)，最壞情況下的時間復(fù)雜度是O(n)。4.2.3優(yōu)缺點 查找的效率較高，但是只適用于有序表，且限于順序存儲結(jié)構(gòu)，對線性鏈表無法有效的進(jìn)行查找，還有二分查找在一些特殊情況下,其查找效率很低,如查找元素是數(shù)列中的第一個元素和最后一個元

12、素。4.2.4 改進(jìn)的方法改進(jìn)后的二分查找算法思路：若k不等于amid，則同時改變low和high的值，使下一次的啊low與k之間的距離盡可能等于k與ahigh之間的距離，為下一次的二分查找k成功提供最大的可能。偽代碼如下：（1） low=0；high=n-1（2） Index=1（3） Mid=(high+low)/2（4） While ( low=high and index=-1)（5） If kamid（9） Low=mid+1（10） High=low+2*pos2（11） Else index=mid（12） Return index注:任意兩個元素ai與aj之間的距離為pos，p

13、os1為k與ahigh之間的距離，pos2為k與alow之間的距離。附錄：源代碼（基于C語言的）#include stdio.h#include stdlib.h#include time.h /*順序查找*/ int SeqSearch(int a , int n, int key) /數(shù)組a1 an存放查找集合，n是數(shù)組中元素的個數(shù)（即查找表的長度），key是要查找的元素 int i;/定義了一個整形變量i i=n;/從后往前把表中的元素與要查找的元素進(jìn)行比較 while (i0 & ai!=key)/*當(dāng)i大于0并且目前找到的元素和要找的元素不相等，則執(zhí)行下一條語句*/ i-; retu

14、rn i;/i的值為0則沒找到，為非0則i為要查找元素的位置 /*二分查找的遞歸*/ int diguisearch(int a,int n,int key)/數(shù)組a1 an存放查找集合，n是數(shù)組中元素的個數(shù)（即查找表的長度），key是要查找的元素 int High,Low,Mid;/定義了整形變量High,Low,Mid Low=0,High=n-1;/選擇查找的最大的范圍 Mid=(Low+High)/2; if (Low=High)|(n=-1) return -1;/數(shù)字-1表示沒有結(jié)果 else if (aMid=key) return Mid; /找到要查找的元素 else if

15、(aMidkey) return (diguisearch(a,Mid-1,key);/需要在左邊的更小的范圍內(nèi)查找 else return (diguisearch(a+Mid+1,n-Mid,key);/在右邊的更大的范圍內(nèi)查找 /二分法非遞歸 int feidiguisearch(int a,int n,int key)/*數(shù)組a1 an存放查找集合，n是數(shù)組中元素的個數(shù)（即查找表的長度），key是要查找的元素*/ int mid;/定義了一個整形變量midint low=0;/定義了一個整形變量low,并且賦值為0int high=n-1;/選擇查找的最大的范圍 while(lowam

16、id) low=mid+1;/在后半?yún)^(qū)間查找 else high=mid-1;/在前半?yún)^(qū)間查找 return -1;/查找失敗void main() int n=200; /定義一個變量n，n=200 int a200; /定義一個數(shù)組a，數(shù)組里數(shù)的個數(shù)是200 int key=59; srand(unsigned)time(NULL); /*初始化隨機函數(shù)種子，這句是拿系統(tǒng)時間作為種子，由于時間是變化的，種子變化，可以產(chǎn)生不相同的隨機數(shù)*/ for(int i=0;in;i+)/初始化變量i的值為0，當(dāng)i=0時執(zhí)行循環(huán)，在每次循環(huán)后i執(zhí)行加1操作 ai=rand()%100; /隨機數(shù)的取值

17、從0到100之間 /*for(int b=0;bn;b+) printf(%d ,ab); */ clock_t start,end; /聲明時間變量 double duration; /聲明用于記錄時間的變量 start=clock();/開始記錄時間 SeqSearch(a,n,key);/計算直接查找規(guī)模為n的時候用的時間 printf(%d,key);/輸出要查找的元素，即key end=clock();/停止記錄時間 duration=(double)(end-start)/CLOCKS_PER_SEC; /求時間差并把時間差記錄在 duration中 printf(nthe Seq

18、Search time is=%f secondsn,duration); /輸出時間差，也就是計算所用的時間 start=clock();/開始記錄時間 diguisearch(a,n,key); /計算二分遞歸查找規(guī)模為n的時候用的時間 printf(%d,key);/輸出要查找的元素，即key end=clock();/停止記錄時間 duration=(double)(end-start)/CLOCKS_PER_SEC;/求時間差并把時間差記錄在duration中 printf(nthe diguisearch time is=%f secondsn,duration); /輸出時間差，也就是計算所用的時間 s