數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告-1-時間復(fù)雜度(1)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告 專業(yè) 13物聯(lián)網(wǎng) 年級 大二 姓名 繆思婷 學(xué)號 1317443007 指導(dǎo)老師 黃河 實(shí)驗(yàn)室 使用日期 實(shí)驗(yàn)三 算法的時間復(fù)雜度一、實(shí)驗(yàn)?zāi)康?、幫助讀者復(fù)習(xí)C語言程序設(shè)計中的知識。2、通過本實(shí)驗(yàn)加深對時間復(fù)雜度的理解。二、實(shí)驗(yàn)內(nèi)容問題描述1. 背景知識：l 時間復(fù)雜度：在計算機(jī)科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運(yùn)行時間。這是一個關(guān)于代表算法輸入值的字符串的長度的函數(shù)。l 冒泡排序冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)

2、排序完成。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端。l 冒泡排序算法的運(yùn)作如下：1) 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。2) 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。3) 針對所有的元素重復(fù)以上的步驟，除了最后一個。4) 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。詳細(xì)算法可以參見以下鏈接：l 選擇排序選擇排序是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然

3、后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢?？梢詤⒁娨韵骆溄樱?. 實(shí)驗(yàn)內(nèi)容：生成8個整數(shù)數(shù)組，分別使用冒泡法，選擇法進(jìn)行排序，并比較排序所消耗的時間。l 8個數(shù)組分為4組，長度為10，100,1000,10000。l 每組數(shù)據(jù)中其中一份數(shù)組中數(shù)據(jù)為隨機(jī)排列，另一份數(shù)組中數(shù)據(jù)為逆序排列（例如9,8,7,6,5,4,3,2,1,0）?；疽螅?） 使用c或c+編寫程序完成上述實(shí)驗(yàn)（2） 可以使用clock函數(shù)獲取計算機(jī)的當(dāng)前時間。clock（）函數(shù)獲得當(dāng)前程序消耗時間（時鐘周期），所以兩次clock之間的差除以CLOCKS_PER_SEC即可獲得當(dāng)前時間消耗的時間（秒），詳細(xì)可以

4、參見clock.cpp文件。三、設(shè)計思路 用rand()函數(shù)，隨機(jī)生成所需要的數(shù)，用系統(tǒng)內(nèi)核內(nèi)定時器的頻率來計算所經(jīng)過的時間。4、 源代碼void SetRand(int Size);void SetSequence(int Size);void bubble_sort(int a,int n); void Select_sort(int R, int n);LARGE_INTEGER start;LARGE_INTEGER end;LARGE_INTEGER freq;int ar10000;int size;int main()while(1)printf("1，設(shè)置隨機(jī)數(shù)個數(shù)n

5、");printf("2，設(shè)置逆序數(shù)個數(shù)n");printf("3，冒泡排序n");printf("4，直接選擇排序n");char select;scanf("%c",&select);switch(select)case '1':printf("請輸入隨機(jī)數(shù)個數(shù):t");scanf("%d",&size); SetRand(size);printf("設(shè)置完成！");break; case '2'

6、;:printf("請輸入逆序數(shù)個數(shù):t");scanf("%d",&size);SetSequence(size);printf("設(shè)置完成！n");break; case'3':int temp10000;for(size=1;arsize>0;size+)tempsize=arsize;QueryPerformanceFrequency(&freq); QueryPerformanceCounter(&start); bubble_sort(temp,size); QueryPerf

7、ormanceCounter(&end); printf("user time : %.10f secondsn", (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart); break;case'4':int temp10000;for(size=1;arsize>0;size+)tempsize=arsize;QueryPerformanceFrequency(&freq); QueryPerformanceCounter(&start); Select_sort(temp,size); QueryPerformanceCounter(&end); printf("user time : %.10f secondsn", (double)(e