欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++用函數(shù)對算法性能進行測試

 更新時間:2022年08月03日 09:17:00   作者:Aricl.  
算法無處不在,算法是程序的靈魂,而數(shù)據(jù)結(jié)構(gòu)則是程序的骨架,二者共同構(gòu)成了程序,那么如何評估算法的性能呢?理論上可以通過計算時間復雜度的方法來評估,但這是理性的認識,我們還有一種直觀的評估方法,那就是程序執(zhí)行的時間

前言

“Algorithm+Data Structures=Programs”——瑞士計算機科學家尼古拉斯·沃斯

工具

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(實際上是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ù)生成。

#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]);	
	}
}
//隨機數(shù)組 
int* RandomArray(int n,int rangeL,int rangeR){
	int *arr=new int[n];//創(chuàng)建一個大小為n的數(shù)組 
	srand(time(NULL));//以時間為"種子"產(chǎn)生隨機數(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()排序算法的性能遠遠遠遠優(yōu)于選擇排序。

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

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

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

相關(guān)文章

  • C語言實現(xiàn)推箱子游戲

    C語言實現(xiàn)推箱子游戲

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)推箱子游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-11-11
  • Matlab利用隨機森林(RF)算法實現(xiàn)回歸預測詳解

    Matlab利用隨機森林(RF)算法實現(xiàn)回歸預測詳解

    這篇文章主要為大家詳細介紹了Matlab如何利用隨機森林(RF)算法實現(xiàn)回歸預測,以及自變量重要性排序的操作,感興趣的小伙伴可以了解一下
    2023-02-02
  • C語言中printf()緩沖問題詳解

    C語言中printf()緩沖問題詳解

    這篇文章主要給大家介紹了關(guān)于C語言中printf()緩沖問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧。
    2017-11-11
  • C語言每日練習之字符串反轉(zhuǎn)

    C語言每日練習之字符串反轉(zhuǎn)

    這篇文章主要介紹了C語言字符串反轉(zhuǎn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-11-11
  • C語言實現(xiàn)學生學籍管理系統(tǒng)程序設(shè)計

    C語言實現(xiàn)學生學籍管理系統(tǒng)程序設(shè)計

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)學生學籍管理系統(tǒng)程序設(shè)計,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-07-07
  • C++中的不規(guī)則二維數(shù)組實現(xiàn)代碼

    C++中的不規(guī)則二維數(shù)組實現(xiàn)代碼

    本文介紹了一個在C++中保存不定長二維數(shù)組的數(shù)據(jù)結(jié)構(gòu),在這個結(jié)構(gòu)中,我們使用了一個含有指針和數(shù)組長度的結(jié)構(gòu)體,用這樣的一個結(jié)構(gòu)體構(gòu)造一個結(jié)構(gòu)體數(shù)組,用于存儲每一個不定長的數(shù)組,感興趣的朋友一起看看吧
    2024-03-03
  • C++ 迭代器失效問題解決

    C++ 迭代器失效問題解決

    在C++中,當一個vector進行了插入或刪除操作時,其迭代器可能會失效,本文就來介紹一下C++ 迭代器失效問題解決,具有一定的參考價值,感興趣的可以了解一下
    2024-01-01
  • 二叉樹中葉子節(jié)點的統(tǒng)計和樹高問題

    二叉樹中葉子節(jié)點的統(tǒng)計和樹高問題

    今天小編就為大家分享一篇關(guān)于二叉樹中葉子節(jié)點的統(tǒng)計和樹高問題,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-03-03
  • 簡要對比C語言中的setgid()函數(shù)和setregid()函數(shù)

    簡要對比C語言中的setgid()函數(shù)和setregid()函數(shù)

    這篇文章主要介紹了C語言中的setgid()函數(shù)和setregid()函數(shù)的簡要對比,是C語言入門學習中的基礎(chǔ)知識,需要的朋友可以參考下
    2015-08-08
  • 快速學習六大排序算法

    快速學習六大排序算法

    這篇文章主要介紹了六大排序算法-插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序,需要學習的小伙伴可以參考這篇文章
    2021-08-08

最新評論