搜索算法效率比較資料

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告搜索算法效率比較的設(shè)計專業(yè)計算機科學(xué)與技術(shù)學(xué)生姓名 Xxxxx班級Xxxx學(xué)號Xxxx指導(dǎo)教師 Xxx完成日期2016年6月16日目 錄1設(shè)計題目3.2. 設(shè)計目的及要求3.2.1目的3.2.2.要求3.3. 設(shè)計內(nèi)容3.4. 設(shè)計分析 4.4.1. 空間復(fù)雜度5.4.2非遞歸線性搜索設(shè)計5.4.3遞歸線性搜索5.4.4二叉搜索設(shè)計6.5. 設(shè)計實踐7.5.1非遞歸線性搜索模塊設(shè)計 7.5.2遞歸線性搜索模塊設(shè)計7.5. 3二叉搜索模塊設(shè)計 7.5.4.主程序模塊設(shè)計8.6測試方法107. 程序運行效果1.18. 設(shè)計心得12搜索算法效率比較的設(shè)計1. 設(shè)計題目給定一個已排

2、序的由N個整數(shù)組成的數(shù)列0,1,2,3,N-1,在該隊列中 查找指定整數(shù)，并觀察不同算法的運行時間?？紤]兩類算法：一個是線性搜索， 從某個方向依次掃描數(shù)列中各個元素；另一個是二叉搜索法。要完成的任務(wù)是： 分別用遞歸和非遞歸實現(xiàn)線性搜索； 分析最壞情況下，兩個線性搜索算法和二叉 搜索算法的復(fù)雜度；測量并比較這三個方法在N=100, 500 , 1000 , 2000,4000,6000,8000 , 10000時的性能。2. 設(shè)計目的及要求2.1 .目的(1) 需要同學(xué)達到熟練掌握C語言的基本知識和技能；(2) 基本掌握面向?qū)ο蟪绦蛟O(shè)計的基本思路和方法；(3) 能夠利用所學(xué)的基本知識和技能，解決

3、簡單的程序設(shè)計問題；2.2 .要求學(xué)生必須仔細閱讀數(shù)據(jù)結(jié)構(gòu)，認真主動完成課設(shè)的要求，有問題及時主動通 過各種方式與教師聯(lián)系溝通；要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間， 安排好課 設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己計劃完成情況；獨立思考， 課程設(shè) 計中各任務(wù)的設(shè)計和調(diào)試哦要求獨立完成， 遇到問題可以討論，可以通過同學(xué)間 相互討論而解決。3. 設(shè)計內(nèi)容任何程序基本上都是要用特定的算法來實現(xiàn)的。 算法性能的好壞，直接決定 了所實現(xiàn)程序性能的優(yōu)劣。此次對有關(guān)算法設(shè)計的基本知識作了簡單的介紹。針 對靜態(tài)查找問題，以搜索算法的不同實現(xiàn)， 并對非遞歸線性搜索算法、遞歸線性 搜索算法和二叉搜索算法這三種方

4、法進行了比較和分析。算法是為求解一個問題需要遵循的、 被清楚地指定的簡單指令的集合。解決一個 問題，可能存在一種以上的算法，當(dāng)這些算法都能正確解決問題時， 算法需要的 資源量將成為衡量算法優(yōu)良度的重要度量，列如算法所需的時間、空間等。算法 是對問題求解過程的一種描述，是為解決一個問題或一類問題給出的一個正確 的，有限長的操作序列。由于查找一個數(shù)的過程，無論運用哪種算法對于電腦來說速度都是非?？?的，都愛1ms之內(nèi)，無法用計時函數(shù)測試出來。所以為了能夠直觀準(zhǔn)確地表示出 各個算法間的差異，此程序用了循環(huán)查找的方法，具體的思想是：先隨機生成3000 個數(shù)作為查找的數(shù)據(jù)源，再隨機生成3000個數(shù)作為被

5、查找的數(shù)，讓當(dāng)前的查找算 法運行一趟，這樣就相當(dāng)于運行了 3000次o這樣還不具有一定的客觀性，用flag標(biāo)記出剛剛運行完查找后的結(jié)果， 從數(shù) 據(jù)源中找到目標(biāo)的數(shù)標(biāo)記為1,沒找到的標(biāo)記為0,并以此存為兩個數(shù)組，最后我 們就可以使用這兩個數(shù)組再次分別進行循環(huán)查找，同時開始計時，如此一來就可以計算出各個算法在查找成功的情況下需要多少時間，反之在沒查找到的情況下 需多長時間了。4. 設(shè)計分析表(List )是用來存放多個相同類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)之一。對表的所有操作 都可以通過使用數(shù)組來實現(xiàn)。在本題目中，使用數(shù)組來存放數(shù)列。雖然數(shù)組是動態(tài)指定的，但是還是需要對表的大小的最大值進行估計。一般需要估計得大一

6、些，從而會浪費一定的空間。本題目中傳遞數(shù)組時，以常數(shù)參數(shù)const a的方式，這樣可以防止在搜索是數(shù)據(jù)被修改。123 N-1兩種線性搜索算法的程序結(jié)構(gòu)分別為以下所示。非遞歸線性搜索從數(shù)組的最 左邊開始，逐個比較，直到找到所搜索的對象或者直到最后搜索失敗。遞歸搜索從最右開始搜索。為什么不從最左邊開始？因為從左邊開始，每次遞歸除要傳遞待處理數(shù)列的左邊界外，還需要傳遞運算數(shù)組的右邊界(即N-1，這在本題目里也是變化的)。從而右邊開始，每次只需傳遞數(shù)組的右邊界(左邊界固定為0)o所謂時間復(fù)雜度：時間復(fù)雜度在剛才提到的時間頻度中，n稱為問題的規(guī)模，當(dāng)n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們

7、想知道它變化時 呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)雜度概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n), 使得當(dāng)n趨近于無窮大時，T(n”f(n)的極限值為不等于零的常數(shù)，則稱f(n)是 T(n)的同數(shù)量級函數(shù)。記作T(n)= O (f(n),稱O (f(n)為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。按數(shù)量級遞增排列，常見的時間復(fù)雜度有：常數(shù)階0(1),對數(shù)階O(log2n),線性階O(n),線性對數(shù)階0(nlog2n),平方階O(n2),立方階 O(n3),. ，k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時

8、 間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。最壞時間復(fù)雜度和平均時間復(fù)雜度：最壞情況下的時間復(fù)雜度稱最壞時間復(fù) 雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上 界，這就保證了算法的運行時間不會比任何更長。在最壞情況下的時間復(fù)雜度為T(n)=0(n)，它表示對于任何輸入實例，該算法的運行時間不可能大于0(n)。平 均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運 行時間。此算法可以通過非遞歸線性搜索，線性遞歸搜索以及二叉法三種來進行搜索 算法效率比較，從中辨析出三種算法中哪種算法最有效。

9、同時在主函數(shù)中用 clock（）來調(diào)用庫函數(shù)4.1. 空間復(fù)雜度一個程序的空間復(fù)雜度是指運行完一個程序所需內(nèi)存的大小。利用程序的空間復(fù)雜度，可以對程序的運行所需要的內(nèi)存多少有個預(yù)先估計。一個程序執(zhí)行時除了需要存儲空間和存儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為現(xiàn)實計算所需信息的輔助空間。 程序執(zhí)行時所需存儲空間包括以下兩部分。固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)。 主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡單變量）等所占的空間。 這部分屬于靜態(tài)空間?？勺兛臻g，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需

10、的空間等。這部分的空間大小與算法有關(guān)。4.2非遞歸線性搜索設(shè)計在一個已知無序隊列中找出與給定關(guān)鍵字相同的數(shù)的具體位置。原理是讓關(guān)鍵字與隊列中的二叔從第一個開始逐個比較， 直到找出與給定關(guān)鍵字相同的數(shù)為 止。它對于表的結(jié)構(gòu)沒有任何要求，其缺點是查找效率低；其優(yōu)點是算法簡單。4.3遞歸線性搜索遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用，是指函數(shù) /過程/子程序在運 行過程序中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象， 程序調(diào)用自身的編程技巧成 為遞歸。一個過程或函數(shù)在其定義或說明中又直接或間接調(diào)用自身的一種方法， 它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題 來求解，遞歸策略只需少

11、量的程序就可描述出解題過程所需要的多次城府計算， 大大地減少了程序的代碼量。遞歸的能力在于用有線的語句來定義對象的無限集 合。用遞歸思想寫出來的程序往往十分簡潔易懂。遞歸就是在過程或函數(shù)里調(diào)用 自身；在使用遞增歸策略時，必須有一個明確的遞歸結(jié)束條件，成為遞歸出口。4.4二叉搜索設(shè)計二叉搜索的算法思想是將數(shù)列按有序化 （遞增或遞減）排列，查找過程中采 用跳躍式方式查找，即先以有序數(shù)列的中點位置為比較對象， 如果要找的元素值 小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。 通過一次比 較，將查找區(qū)間縮小一般。流程圖:5. 設(shè)計實踐5.1非遞歸線性搜索模塊設(shè)計非遞歸線性搜索的特點在于它

12、的，每一次進行搜索時總是從數(shù)組的最左邊開 始，逐個比較，直到找到所搜索的對象或者直到最后搜索失敗。int IterativeSequentialSearch(const int a,int x,int n) int i;for(i=0;ik,則中點值之后的數(shù)都大于k，所以k值在該表的左邊，所以確定一個新的查找區(qū)間；如果中點值k，則中點值之后的數(shù)都小于k，k值在該表的右邊， 再在 該表的右邊確定一個新的查找區(qū)間；依次循環(huán)。它的核心程序如下：int Bin arySearch(c onst int a,i nt x,i nt n) int low,mid,high; low=0;high=n-1;

13、while(lowx) low=mid+1;else if(amidx) high=mid-1; else return mid; return -1; 對于輸入數(shù)據(jù)量很大時，線性搜索的時間太慢，不宜使用。二叉搜索采用折 半的思想，它的運行時間為 O(log2N)，比線性搜索要快許多，特別是在處理的 數(shù)據(jù)量比較大的時候非常有用。54主程序模塊設(shè)計此程序的作用是分別進行了定義，調(diào)用函數(shù)。并且通過clock()函數(shù)調(diào)用庫函數(shù)。程序如下：int mai n ()/* clock() 返回函數(shù)運行時間*/int i,n ,x,a10000;long k,l;prin tf(Please en ter

14、n:n);scan f(%d,&n);/*if(n 10000)prin tf(error!); return -1;x=n;/*輸入數(shù)據(jù)*/*處理異常輸入*/for(i=0;in;i+) /*指定要查找的數(shù)*/數(shù)組初始化*/ai=i;prin tf(Pleaseenter iterations:n); /*為了更準(zhǔn)確地計算運行時間，我們可以重復(fù)多次調(diào)用算法，再取平均值 */scan f(%ld,&k);if(k1)/* 處理異常輸入*/prin tf(error!);return -1;非遞歸線性搜索start = clock(); /*記錄函數(shù)的開始時間*/for(l=0;lk;l+)It

15、erativeSeque ntialSearch(a,x, n);stop = clock(); /*記錄函數(shù)的結(jié)束時間*/計算函數(shù)運行時間durati on = (double)(stop - start)/CLK_TCK; /*/prin tf(nlterativeSeque ntialSearch:n Iteratio ns:%ldnTicks:%d nTotalTime:%.8lfnDuratio n: %.8lfn,k,(i nt)(stop-start),duratio n,duratio n/k);/*輸出花費時間*/遞歸線性搜索start = clock(); /*記錄函數(shù)的開

16、始時間*/for(l=0;lk;l+)RecursiveSeque ntialSearch(a,x, n);stop = clock(); /*記錄函數(shù)的結(jié)束時間*/計算函數(shù)運行時間durati on = (double)(stop - start)/CLK_TCK; /*/prin tf(nRecursiveSeque ntialSearch:n Iterati on s:%ldnTicks:%dnTotalTime:%.8lfnDuratio n: %.8lfn,k,(i nt)(stop-start),duratio n,duratio n/k);/* 輸出花費時間*/*-二 叉搜*/p

17、rin tf(niteratio ns of Binary Search is 100 times of iterati ons more tha n other two searchsn);k=100*k; /*由于二叉搜索的時間比較快，為了避免出現(xiàn)0秒，二叉搜索算法調(diào)用的次數(shù)是線性搜索的100倍*/start = clock(); /* 記錄函數(shù)的開始時間*/ for(l=0;l00 谿00 kh 3 - 1. f I 5 I- 0 -H-0M 0霜 2.尼日勻. =S *hb窪s： Any ke v to con t nue當(dāng)輸入的值有錯誤的時候，表示所輸入的值不在所規(guī)定的范圍內(nèi)時， 會

18、出現(xiàn) 以下的界面：8.設(shè)計心得在這次課程設(shè)計里，也讓我從中有所收獲。雖說只有一個禮拜，但在課后還 是花了不少時間?？唇滩闹械某绦驎r，發(fā)現(xiàn)一個程序設(shè)計就是算法與數(shù)據(jù)結(jié)構(gòu)的 結(jié)合體，看程序有時都看不懂，更別提自己編譯了，覺得自己在這方面需要掌握 的內(nèi)容還有很多狠多。雖然過程曲折可謂一語難盡。整天都是對著電腦，不然就是翻閱資料。這次課程設(shè)計使我體會到只有做到細心耐心，恒心才能做好事情。課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識 ，發(fā)現(xiàn),提出，分析和解決實際問題， 鍛煉實踐能力的重要環(huán)節(jié)，是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程 .同時 加強了我們動手、思考和解決問題的能力。鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解。培 養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分 析問題，解決問題的能力。而且做課程設(shè)計同時也是對課本知識的鞏固和加強， 平時看課本是，有些問題就不是很能理解， 做完課程設(shè)計，那些問題就迎刃而解 了