第C++用函數(shù)對算法性能進行測試目錄前言工具模板說明測試

前言

Algorithm+DataStructures=Programs瑞士計算機科學(xué)家尼古拉斯沃斯

工具

C/C++庫函數(shù)中的time.h/ctime庫中的clock()函數(shù)

模板

usingnamespacestd;

clock_tstart_time=clock();

{算法代碼塊};

clock_tend_time=clock();

cout(double)(end_time-start_time)/CLOCKS_PER_SEC秒

說明

clock()函數(shù)返回類型為clock_t（實際上是long類型），它返回從開啟某個程序進程到再次調(diào)用clock()函數(shù)之間的CPU時鐘計時單元（時鐘周期）。

CLOCKS_PER_SEC是標準庫中所定義的宏，表示每1秒CPU時鐘計時單元（時鐘周期）的個數(shù)

end_time-start_time表示該程序執(zhí)行期間CPU時鐘計時單元（時鐘周期）的總個數(shù)，除以每秒鐘CPU時鐘計時單元（時鐘周期），即可得到程序?qū)嶋H運行時間，返回的單位是毫秒。

測試

分別測試選擇排序算法和C++中的sort()函數(shù)的算法性能，測試數(shù)據(jù)由隨機數(shù)生成。

#includeiostream

#includealgorithm

#includectime

usingnamespacestd;

//選擇排序

voidSelectSort(inta[],intn){

for(inti=0;ii++){

intmin_index=i;

for(intj=i+1;jj++)

if(a[j]a[min_index])

min_index=j;

swap(a[i],a[min_index]);

//隨機數(shù)組

int*RandomArray(intn,intrangeL,intrangeR){

int*arr=newint[n];//創(chuàng)建一個大小為n的數(shù)組

srand(time(NULL));//以時間為"種子"產(chǎn)生隨機數(shù)

for(inti=0;ii++){

arr[i]=rand()%(rangeR-rangeL+1)+rangeL;//生成指定區(qū)間[rangeL,rangeR]里的數(shù)

returnarr;

intmain(){

intn;

cout"請輸入數(shù)據(jù)規(guī)模n:";cinn;

int*arr1,*arr2;

arr1=RandomArray(n,0,10000);

arr2=arr1;

clock_tstart_time1=clock();

SelectSort(arr1,n);//選擇排序算法

clock_tend_time1=clock();

cout"選擇排序耗時："(double)(end_time1-start_time1)/CLOCKS_PER_SEC"秒"endl;

clock_tstart_time2=clock();

sort(arr2,arr2+n);//C++中sort()排序函數(shù)，底層為優(yōu)化的快速排序算法

clock_tend_time2=clock();

cout"優(yōu)化快排耗時："(double)(end_time2-start_time2)/CLOCKS_PER_SEC"秒"endl;

return0;

}

測試結(jié)果

測試結(jié)果分析

通過對比可知，在數(shù)據(jù)規(guī)模相同的情況下，C++sort()排序算法的性能遠遠遠遠優(yōu)于選擇排序。

我們能從數(shù)據(jù)上直觀的看到數(shù)據(jù)規(guī)模的增長所帶來的運行時間的加長，數(shù)據(jù)規(guī)模由10000變?yōu)?00000，擴大了10倍，那么根據(jù)時間復(fù)雜度的分析，選擇排序的算法時間會擴大100倍左右，而sort()排序函數(shù)則會擴大10倍左右，由測試結(jié)果看出，確實如此。

因為選擇排序算法的時間復(fù)雜度為O（n^2），而C++sort()排序函數(shù)的底層實現(xiàn)原理是快速排序算法，而且是優(yōu)化的快速排序，系統(tǒng)會根據(jù)數(shù)據(jù)形式和數(shù)據(jù)量自動選擇合適的排序方法。它每次排序中不只選擇一種方法，比如給一個數(shù)據(jù)量較大的數(shù)組排序，開始采用快速排序，