各種查找算法性能分析

1、項(xiàng) 目 名 稱：各種查找算法的性能測(cè)試項(xiàng)目成員：組編號(hào)：完成時(shí)間： 目錄前言.2正文.2第1章 簡(jiǎn)介.2 1.1順序查找問(wèn)題描述 .2 1.2二分查找問(wèn)題描述 .2 第2章 算法定義.22.1順序查找算法定義.2 2.2二分查找算法定義.3 第3章 測(cè)試結(jié)果（Testing Results).5 3.1 實(shí)驗(yàn)結(jié)果表 .5 3.2 散點(diǎn)圖記錄 .5第4章 分析和討論.6 4.1順序查找分析 .6 4.2二分查找分析 .6附錄：源代碼（基于C語(yǔ)言的).7聲明 .13前言查找問(wèn)題就是在給定的集合（或者是多重集，它允許多個(gè)元素具有相同的值）中找尋一個(gè)給定的值，我

2、們稱之為查找鍵。 對(duì)于查找問(wèn)題來(lái)說(shuō)，沒(méi)有一種算法在任何情況下是都是最優(yōu)的。有些算法速度比其他算法快，但是需要較多的存儲(chǔ)空間；有些算法速度非?？欤珒H適用于有序數(shù)組。查找問(wèn)題沒(méi)有穩(wěn)定性的問(wèn)題，但會(huì)發(fā)生其他的問(wèn)題（動(dòng)態(tài)查找表）。在數(shù)據(jù)結(jié)構(gòu)課程中，我們已經(jīng)學(xué)過(guò)了幾種查找算法，比較有代表性的有順序查找（蠻力查找），二分查找 （采用分治技術(shù)），哈希查找（理論上來(lái)講是最好的查找方法）。第一章：簡(jiǎn)介（Introduction）1.1順序查找問(wèn)題描述：順序查找從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個(gè)記錄，其關(guān)鍵

3、字和給定值比較都不等，則表明表中沒(méi)有所查記錄，查找不成功。1.2二分查找問(wèn)題描述：（1）分析掌握折半查找算法思想，在此基礎(chǔ)上，設(shè)計(jì)出遞歸算法和循 環(huán)結(jié)構(gòu)兩種實(shí)現(xiàn)方法的折半查找函數(shù)。（2）編寫程序?qū)崿F(xiàn)：在保存于數(shù)組ai有序數(shù)據(jù)元素中查找數(shù)據(jù)元素k是否存在。數(shù)元素k要包含兩種情況：一種是數(shù)據(jù)元素k包含在數(shù)組中；另一種是數(shù)據(jù)元素k不包含在數(shù)組中（3）數(shù)組中數(shù)據(jù)元素的有序化既可以初始賦值時(shí)實(shí)現(xiàn)，也可以設(shè)計(jì)一個(gè)排序函數(shù)實(shí)現(xiàn)。（4）根據(jù)兩種方法的實(shí)際運(yùn)行時(shí)間，進(jìn)行兩種方法時(shí)間效率的分析對(duì)比。第二章：算法定義（Algorithm Specification）2.1順序查找從表的一端向另一端逐個(gè)進(jìn)行記錄的關(guān)鍵

4、字和給定值（要查找的元素）的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查找記錄；反之，若直至第一個(gè)記錄，其關(guān)鍵字和給定值比較都不等，則表明表中沒(méi)有所查記錄，查找不成功。順序查找的算法如下：int SeqSearch1(int r , int n, int k) /數(shù)組r1 rn存放查找集合，n是數(shù)組中元素的個(gè)數(shù)（即查找表的長(zhǎng)度），k是要查找的元素 i=n;/從后往前把表中的元素與要查找的元素進(jìn)行比較 while (i>0 && ri!=k)/當(dāng)i>0并且數(shù)組元素中的值不等于要查找元素時(shí)，i減一繼續(xù)執(zhí)行while循環(huán) i-; return i;/i的

5、值為0則沒(méi)找到，為非0則i為要查找元素的位置 2.2二分查找二分查找又稱折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中間的那個(gè)元素，則找到要查找的元素，查找成功；如果要查找的元素比中間的那個(gè)元素小則使用相同的策略只在左邊的區(qū)間查找就可以；如果要查找的元素比中間的那個(gè)元素大，則使用相同的策略在右邊的區(qū)間進(jìn)行查找；每次將待查找的元素的所在區(qū)間縮小一半。（1）二分查找算法的遞歸算法int binary_search_2(int a,int n,int k)/遞歸的二分查找算法的偽代碼：查找表放在數(shù)組a中，n是查找表中元素的個(gè)數(shù)，k是待查找的元素 int Low,Mid,Hig

6、h;Low=0,High=n-1;/選擇查找的最大的范圍 Mid=(Low+High)/2; /quicksort(a,0,SIZE-1);if (Low>=High) return -1;/數(shù)字-1表示沒(méi)有結(jié)果 if (aMid=k) return Mid; /找到要查找的元素 else if (aMid>k) return (binary_search_2(a,Mid-1,k);/需要在左邊的更小的范圍內(nèi)查找 else return (binary_search_2(a+Mid+1,High-Mid,k);/在右邊的更大的范圍內(nèi)查找 （2）二分查找的非遞歸算法int binar

7、y_search_1(int a,int n,int k) /非遞歸的二分查找算法的偽代碼：查找表放在數(shù)組a中，n是查找表中元素的個(gè)數(shù)，k是待查找的元素 int Low,High,i,mid; Low=0; High=n-1; while(Low<High) mid=(Low+High)/2;if(k=amid)return mid;/查找成功else if(k>amid)Low=mid+1;/在后半?yún)^(qū)間查找else High=mid-1;/在前半?yún)^(qū)間查找return 0;/查找失敗第3章 ：測(cè)試結(jié)果（Testing Results）3.1實(shí)驗(yàn)結(jié)果表： 查找算法隨機(jī)數(shù)組元素個(gè)數(shù)（個(gè)

8、）查找時(shí)間（seconds） 順序查找20.02200040.04700060.062000 80.082000 100.100000 二分查找 20.19000040.39000060.39000080.060000100.060000 3.2散點(diǎn)圖：注釋：橫軸為數(shù)組元素個(gè)數(shù)，縱軸為(查找時(shí)間/1000)。 第四章：分析和討論4.1.實(shí)現(xiàn)順序查找算法：（1）順序查找算法思路很簡(jiǎn)單，就是一種遍歷的思想，一個(gè)個(gè)查找目標(biāo)元素，實(shí)現(xiàn)也很簡(jiǎn)單。（2）對(duì)于有n個(gè)元素的表適用順序查找。比較次數(shù)：不成功：比較n次。成功查找：最好的情況為1次，即第一個(gè)元素即為目標(biāo)元素；最差的情況為n次；平均比較次數(shù)（n+1）

9、/2次。所以當(dāng)表很大時(shí)，順序查找的代價(jià)是很大的。（3）順序查找算法不會(huì)有重復(fù)的比較出現(xiàn)，即一旦找到即成功，但同時(shí)這種代價(jià)是當(dāng)表中有重復(fù)的目標(biāo)元素時(shí)（比如有多個(gè)目標(biāo)元素）我們只能得到第一個(gè)元素的位置。順序查找算法時(shí)間復(fù)雜度為O(n)。4.2實(shí)現(xiàn)二分查找算法：（1）二分查找法思路：遞增排列的表，首先從中間元素開(kāi)始查找，如果元素比目標(biāo)元素小，則查找后半部分表，反之查找前半部分表，并重復(fù)這一過(guò)程。這樣每次查找中我們都把表的長(zhǎng)度減半。（2）二分查找在實(shí)現(xiàn)中有量Low和High，每次減半的過(guò)程體現(xiàn)在Low和High的改變上，在代碼的實(shí)現(xiàn)上可以使用單純的循環(huán)或者用函數(shù)遞歸的思想。遞歸思想更容易理解，但編寫之

10、后我們發(fā)現(xiàn)函數(shù)是尾遞歸，尾遞歸通?？梢杂煤?jiǎn)單的循環(huán)實(shí)現(xiàn)，循環(huán)在操作來(lái)說(shuō)沒(méi)有了函數(shù)調(diào)用的過(guò)程，更節(jié)省時(shí)間和空間。（3）編碼中小小地方的改動(dòng)可能對(duì)程序有很大的改觀。如上述兩種二分查找非遞歸binary_search_1（不比較等于的情況）遞歸binary_search_2（添加等于情況）折半搜索，也稱二分查找算法、二分搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜素過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。這

11、種搜索算法每一次比較都使搜索范圍縮小一半。時(shí)間復(fù)雜度：二分搜索每次把搜索區(qū)域砍掉一半，很明顯時(shí)間復(fù)雜度為O(lgn)或O(n)。（n代表集合中元素的個(gè)數(shù)）空間復(fù)雜度：雖以遞歸形式定義，但是尾遞歸，可改寫為循環(huán),所以空間復(fù)雜度為 O(n)=O(lgn)。附錄：源代碼（基于C語(yǔ)言的）#include "stdio.h"#include "time.h"#include "stdlib.h"#define SIZE 1000/待排數(shù)的規(guī)模#define PRT_RT 1/是否顯示排序前后的數(shù)組情況，對(duì)較大規(guī)模的數(shù)組不顯示 /0為不顯示，1為

12、顯示/順序查找算法int SeqSearch1(int r , int n, int k) /數(shù)組r1 rn存放查找集合，n是數(shù)組中元素的個(gè)數(shù)（即查找表的長(zhǎng)度），k是要查找的元素 int i=n;/從后往前把表中的元素與要查找的元素進(jìn)行比較 while(i>0 && ri!=k) i-; return i;/i的值為0則沒(méi)找到，為非0則i為要查找元素的位置 /二分查找的遞歸算法int binary_search_2(int a,int n,int k)/遞歸的二分查找算法的偽代碼：查找表放在數(shù)組a中，n是查找表中元素的個(gè)數(shù)，k是待查找的元素 int Low,Mid,Hig

13、h;Low=0,High=n-1;/選擇查找的最大的范圍 Mid=(Low+High)/2; if (Low>=High) return -1;/數(shù)字-1表示沒(méi)有結(jié)果 if (aMid=k) return Mid; /找到要查找的元素 else if (aMid>k) return (binary_search_2(a,Mid-1,k);/需要在左邊的更小的范圍內(nèi)查找 else return (binary_search_2(a+Mid+1,High-Mid,k);/在右邊的更大的范圍內(nèi)查找 /二分查找的非遞歸算法int binary_search_1(int a,int n,in

14、t k) int Low,High,i,mid; Low=0; High=n-1; while(Low<High) mid=(Low+High)/2;if(k=amid)return mid;/查找成功else if(k>amid)Low=mid+1;/在后半?yún)^(qū)間查找else High=mid-1;/在前半?yún)^(qū)間查找return 0;/查找失敗/快速排序算法void quicksort(int c,int start,int end)int i,j,mid;i=start;j=end;mid=ci;while(start>=end)return;while(i<j)whi

15、le(i<j && cj>mid)j-; if(i<j)ci=cj;i+;while(i<j && ci<mid)i+;if(i<j)cj=ci;j-;ci=mid;quicksort(c,start,i-1);/遞歸調(diào)用快速排序繼續(xù)對(duì)前半部分的元素進(jìn)行排序quicksort(c,i+1,end);/ 遞歸調(diào)用快速排序繼續(xù)對(duì)后半部分的元素進(jìn)行排序int main()/主函數(shù)int i,j;long start,end;/聲明時(shí)間變量double duration;/聲明用來(lái)記錄時(shí)間的變量 int *a;a=(int*)mall

16、oc(sizeof(int)*SIZE);/分配SIZE字節(jié)的存儲(chǔ)區(qū)srand(unsigned)time(NULL);for(i=0;i<SIZE;i+)/隨機(jī)賦值ai=rand()%SIZE;/取0,SIZE)之間的隨機(jī)整數(shù)if(PRT_RT = 0)printf("%d ",ai);/輸出這個(gè)數(shù)組printf("n");printf("請(qǐng)輸入順序查找要查找的元素:n");scanf("%d",&j);printf("輸出該元素的下標(biāo):%dn",SeqSearch1(a, SI

17、ZE, j);/以下統(tǒng)計(jì)順序查找的運(yùn)行時(shí)間 start=clock(); SeqSearch1(a,SIZE,j); /在這里插入你要計(jì)算時(shí)間的算法，這里計(jì)算的是冒泡排序算法當(dāng)輸入規(guī)模為SIZE的時(shí)候的算法的時(shí)間end = clock();duration=(double)(end-start)/CLOCKS_PER_SEC;printf("the SeqSearch1 time is:%fn",duration);/輸出時(shí)間 /以下顯示順序查找排序結(jié)果if(PRT_RT = 0) quicksort(a,0,SIZE-1);for(i=0; i<SIZE; i+)p

18、rintf("%d ", ai);printf("n");system("pause");printf("請(qǐng)輸入遞歸二分查找要查找的元素：n");scanf("%d",&j);printf("輸出該元素的下標(biāo)：%dn",binary_search_2(a,SIZE,j);/以下統(tǒng)計(jì)遞歸二分查找的運(yùn)行時(shí)間 start = clock(); binary_search_2(a, SIZE, i); end = clock(); duration = (double)(end-start)/CLOCKS_PER_SEC; printf("the search time is :%fn",duration);/輸出時(shí)間system("pause");printf("請(qǐng)輸入非遞歸二分查找要查找的元素：n");scanf("%d",&j);printf("輸出該元素的下標(biāo)：%dn",binary_search_1(a,SIZE,