快捷導(dǎo)航

C++用函數(shù)對(duì)算法性能進(jìn)行測(cè)試

更新時(shí)間：2022年08月03日 09:17:00 作者：Aricl.

算法無處不在，算法是程序的靈魂，而數(shù)據(jù)結(jié)構(gòu)則是程序的骨架，二者共同構(gòu)成了程序，那么如何評(píng)估算法的性能呢？理論上可以通過計(jì)算時(shí)間復(fù)雜度的方法來評(píng)估，但這是理性的認(rèn)識(shí)，我們還有一種直觀的評(píng)估方法，那就是程序執(zhí)行的時(shí)間

前言

“Algorithm+Data Structures=Programs”——瑞士計(jì)算機(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類型），它返回從開啟某個(gè)程序進(jìn)程到再次調(diào)用clock()函數(shù)之間的CPU時(shí)鐘計(jì)時(shí)單元（時(shí)鐘周期）。

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

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

測(cè)試

分別測(cè)試選擇排序算法和C++中的sort()函數(shù)的算法性能，測(cè)試數(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)建一個(gè)大小為n的數(shù)組 
	srand(time(NULL));//以時(shí)間為"種子"產(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<<"請(qǐng)輸入數(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<<"選擇排序耗時(shí)："<<(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)化快排耗時(shí)："<<(double)(end_time2-start_time2)/CLOCKS_PER_SEC<<"秒"<<endl; 
	return 0;
}

測(cè)試結(jié)果

測(cè)試結(jié)果分析

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

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

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

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

您可能感興趣的文章: