前言

“Algorithm+Data Structures=Programs”——瑞士計算機(jī)科學(xué)家尼古拉斯·沃斯

工具

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

模板

#include<iostream>

#include<ctime>

using namespace std;

clock_t start_time = clock();

{ 算 法 代 碼 塊 };

clock_t end_time = clock();

cout<<(double)(end_time - start_time) / CLOCKS_PER_SEC<<"秒";

說明

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

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

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

測試

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

#include<iostream>
#include<algorithm> 
#include<ctime>
using namespace std;
//選擇排序 
void SelectSort(int a[],int n){
	for(int i=0;i<n;i++){
		int min_index=i;
		for(int j=i+1;j<n;j++)
			if(a[j]<a[min_index])
			  min_index=j;
		swap(a[i],a[min_index]);	
	}
}
//隨機(jī)數(shù)組 
int* RandomArray(int n,int rangeL,int rangeR){
	int *arr=new int[n];//創(chuàng)建一個大小為n的數(shù)組 
	srand(time(NULL));//以時間為"種子"產(chǎn)生隨機(jī)數(shù) 
	for(int i=0;i<n;i++){
		arr[i]=rand()%(rangeR-rangeL+1)+rangeL;//生成指定區(qū)間[rangeL,rangeR]里的數(shù) 
	}
	return arr;
}
int main(){
	int n;
	cout<<"請輸入數(shù)據(jù)規(guī)模n: ";cin>>n;
	int *arr1,*arr2;
	arr1=RandomArray(n,0,10000);
	arr2=arr1; 
	clock_t start_time1=clock();
	SelectSort(arr1,n);//選擇排序算法 
	clock_t end_time1=clock();
	cout<<"選擇排序耗時："<<(double)(end_time1-start_time1)/CLOCKS_PER_SEC<<"秒"<<endl;
	clock_t start_time2=clock();
	sort(arr2,arr2+n);//C++中sort()排序函數(shù)，底層為優(yōu)化的快速排序算法 
	clock_t end_time2=clock();
	cout<<"優(yōu)化快排耗時："<<(double)(end_time2-start_time2)/CLOCKS_PER_SEC<<"秒"<<endl; 
	return 0;
} 

測試結(jié)果

測試結(jié)果分析

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

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

因為選擇排序算法的時間復(fù)雜度為O（n^2），而C++sort()排序函數(shù)的底層實(shí)現(xiàn)原理是快速排序算法，而且是優(yōu)化的快速排序，系統(tǒng)會根據(jù)數(shù)據(jù)形式和數(shù)據(jù)量自動選擇合適的排序方法。它每次排序中不只選擇一種方法，比如給一個數(shù)據(jù)量較大的數(shù)組排序，開始采用快速排序，分段遞歸，分段之后每一段的數(shù)據(jù)量達(dá)到一個較小值后它就不繼續(xù)往下遞歸，而是選擇插入排序，如果遞歸的太深，他則會選擇堆排序，時間復(fù)雜度為O（nlogn）。可見C++中sort()排序算法性能之強(qiáng)悍！(吶喊)

到此這篇關(guān)于C++用函數(shù)對算法性能進(jìn)行測試的文章就介紹到這了,更多相關(guān)C++性能測試內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論