尽管有很多因素影响，但是还是可以对自己程序的运行时间有一个大体的评估的。

引用算法4里面的一段话：

火箭科学家需要大致知道一枚试射火箭的着陆点是在大海里还是在城市中；

医学研究者需要知道一次药物测试是会杀死还是会治愈实验对象；

所以 「任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年」。

这个是最基本的，所以以上误差就不算事了。

以下以C++代码为例：

测试硬件：2015年MacPro，CPU配置：2.7 GHz Dual-Core Intel Core i5

实现三个函数，时间复杂度分别是 O(n) , O(n^2), O(nlogn)，使用加法运算来统一测试。

// O(n)

voidfunction1( longlongn) {

longlongk = 0;

for( longlongi = 0; i < n; i++) {

k++;

}

}

// O(n^2)

voidfunction2( longlongn) {

longlongk = 0;

for( longlongi = 0; i < n; i++) {

for( longj = 0; j < n; j++) {

k++;

}

}

}

// O(nlogn)

voidfunction3( longlongn) {

longlongk = 0;

for( longlongi = 0; i < n; i++) {

for( longlongj = 1; j < n; j = j * 2) { // 注意这里j=1

k++;

}

}

}

来看一下这三个函数随着n的规模变化，耗时会产生多大的变化，先测function1 ，就把 function2 和 function3 注释掉

intmain{

longlongn; // 数据规模

while( 1) {

cout<< "输入n：";

cin>> n;

milliseconds start_time = duration_cast(

system_clock::now.time_since_epoch

);

function1(n);

// function2(n);

// function3(n);

milliseconds end_time = duration_cast(

system_clock::now.time_since_epoch

);

cout<< "耗时:"<< milliseconds(end_time).count - milliseconds(start_time).count

<< " ms"<< endl;

}

}

来看一下运行的效果，如下图：

O(n)的算法，1s内大概计算机可以运行 5 * (10^8)次计算，可以推测一下O(n^2) 的算法应该1s可以处理的数量级的规模是 5 * (10^8)开根号，实验数据如下。

O(n^2)的算法，1s内大概计算机可以运行 22500次计算，验证了刚刚的推测。

在推测一下O(nlogn)的话， 1s可以处理的数据规模是什么呢？

理论上应该是比 O(n)少一个数量级，因为logn的复杂度 其实是很快，看一下实验数据。

O(nlogn)的算法，1s内大概计算机可以运行 2 * (10^7)次计算，符合预期。

这是在我个人PC上测出来的数据，不能说是十分精确，但数量级是差不多的，大家也可以在自己的计算机上测一下。

「整体测试数据整理如下：」

至于O(logn) 和O(n^3) 等等这些时间复杂度在1s内可以处理的多大的数据规模，大家可以自己写一写代码去测一下了。

完整测试代码# include

# include

# include

usingnamespacestd;

usingnamespacechrono;

// O(n)

voidfunction1( longlongn) {

longlongk = 0;

for( longlongi = 0; i < n; i++) {

k++;

}

}

// O(n^2)

voidfunction2( longlongn) {

longlongk = 0;

for( longlongi = 0; i < n; i++) {

for( longj = 0; j < n; j++) {

k++;

}

}

}

// O(nlogn)

voidfunction3( longlongn) {

longlongk = 0;

for( longlongi = 0; i < n; i++) {

for( longlongj = 1; j < n; j = j * 2) { // 注意这里j=1

k++;

}

}

}

intmain{

longlongn; // 数据规模

while( 1) {

cout<< "输入n：";

cin>> n;

milliseconds start_time = duration_cast(

system_clock::now.time_since_epoch

);

function1(n);

// function2(n);

// function3(n);

milliseconds end_time = duration_cast(

system_clock::now.time_since_epoch

);

cout<< "耗时:"<< milliseconds(end_time).count - milliseconds(start_time).count

<< " ms"<< endl;

}

}

总结

本文详细分析了在leetcode上做题程序为什么会有超时，以及从硬件配置上大体知道CPU的执行速度，然后亲自做一个实验来看看O(n)的算法，跑一秒钟，这个n究竟是做大，最后给出不同时间复杂度，一秒内可以运算出来的n的大小。

建议大家也都自己做一做实验，测一测，看看是不是和我的测出来的结果差不多。

这样，大家应该对程序超时时候的数据规模有一个整体的认识了。返回搜狐，查看更多