專題講座資料（2021-2022年）各種查找算法性能分析

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

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

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

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

5、值為0則沒找到，為非0則i為要查找元素的位置 2.2二分查找二分查找又稱折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中間的那個元素，則找到要查找的元素，查找成功；如果要查找的元素比中間的那個元素小則使用相同的策略只在左邊的區(qū)間查找就可以；如果要查找的元素比中間的那個元素大，則使用相同的策略在右邊的區(qū)間進行查找；每次將待查找的元素的所在區(qū)間縮小一半。（1）二分查找算法的遞歸算法int binary_search_2(int a,int n,int k)/遞歸的二分查找算法的偽代碼：查找表放在數(shù)組a中，n是查找表中元素的個數(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表示沒有結果 if (aMid=k) return Mid; /找到要查找的元素 else if (aMid>k) return (binary_search_2(a,Mid-1,k);/需要在左邊的更小的范圍內查找 else return (binary_search_2(a+Mid+1,High-Mid,k);/在右邊的更大的范圍內查找 （2）二分查找的非遞歸算法int binar

7、y_search_1(int a,int n,int k) /非遞歸的二分查找算法的偽代碼：查找表放在數(shù)組a中，n是查找表中元素的個數(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章 ：測試結果（Testing Results）3.1實驗結果表： 查找算法隨機數(shù)組元素個數(shù)（個

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

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

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

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

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

13、h;Low=0,High=n-1;/選擇查找的最大的范圍 Mid=(Low+High)/2; if (Low>=High) return -1;/數(shù)字-1表示沒有結果 if (aMid=k) return Mid; /找到要查找的元素 else if (aMid>k) return (binary_search_2(a,Mid-1,k);/需要在左邊的更小的范圍內查找 else return (binary_search_2(a+Mid+1,High-Mid,k);/在右邊的更大的范圍內查找 /二分查找的非遞歸算法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);/遞歸調用快速排序繼續(xù)對前半部分的元素進行排序quicksort(c,i+1,end);/ 遞歸調用快速排序繼續(xù)對后半部分的元素進行排序int main()/主函數(shù)int i,j;long start,end;/聲明時間變量double duration;/聲明用來記錄時間的變量 int *a;a=(int*)mall

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

17、ZE, j);/以下統(tǒng)計順序查找的運行時間 start=clock(); SeqSearch1(a,SIZE,j); /在這里插入你要計算時間的算法，這里計算的是冒泡排序算法當輸入規(guī)模為SIZE的時候的算法的時間end = clock();duration=(double)(end-start)/CLOCKS_PER_SEC;printf("the SeqSearch1 time is:%fn",duration);/輸出時間 /以下顯示順序查找排序結果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("請輸入遞歸二分查找要查找的元素：n");scanf("%d",&j);printf("輸出該元素的下標：%dn",binary_search_2(a,SIZE,j);/以下統(tǒng)計遞歸二分查找的運行時間 start = clock(); binary_search_2(a, SIZE, i); end = clock(); duration = (double)(end-start)/CLOCKS_PER_SEC; printf("the search time is :%fn",duration);/輸出時間system("pause");printf("請輸入非遞歸二分查找要查找的元素：n");scanf("%d",&j);printf("輸出該元素的下標：%dn",binary_search_1(a,SIZE,