O(n)的算法居然超时了，此时的n究竟是多大？
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
# 程序提交之后为什么会超时？O(n)的算法会超时，n究竟是多大？ 一些同学可能对计算机运行的速度还没有概念，就是感觉计算机运行速度应该会很快，那么在leetcode上做算法题目的时候为什么会超时呢？ 计算机究竟1s可以执行多少次操作呢？ 接下来探讨一下这个问题。 ## 超时是怎么回事  大家在leetcode上练习算法的时候应该都遇到过一种错误是“超时”。 也就是说程序运行的时间超过了规定的时间，一般OJ（online judge）的超时时间就是1s，也就是用例数据输入后最多要1s内得到结果，暂时还不清楚leetcode的判题规则，下文为了方便讲解，暂定超时时间就是1s。 如果写出了一个O(n)的算法 ，其实可以估算出来n是多大的时候算法的执行时间就会超过1s了。 如果n的规模已经足够让O(n)的算法运行时间超过了1s，就应该考虑log(n)的解法了。 ## 从硬件配置看计算机的性能 计算机的运算速度主要看CPU的配置，以2015年MacPro为例，CPU配置：2.7 GHz Dual-Core Intel Core i5 。 也就是 2.7 GHz 奔腾双核，i5处理器，GHz是指什么呢，1Hz = 1/s，1Hz 是CPU的一次脉冲（可以理解为一次改变状态，也叫时钟周期），称之为为赫兹，那么1GHz等于多少赫兹呢 * 1GHz（兆赫）= 1000MHz（兆赫） * 1MHz（兆赫）= 1百万赫兹 所以 1GHz = 10亿Hz，表示CPU可以一秒脉冲10亿次（有10亿个时钟周期），这里不要简单理解一个时钟周期就是一次CPU运算。 例如1 + 2 = 3，cpu要执行四次才能完整这个操作，步骤一：把1放入寄存机，步骤二：把2放入寄存器，步骤三：做加法，步骤四：保存3。 而且计算机的cpu也不会只运行我们自己写的程序上，同时cpu也要执行计算机的各种进程任务等等，我们的程序仅仅是其中的一个进程而已。 所以我们的程序在计算机上究竟1s真正能执行多少次操作呢？ ## 做个测试实验 在写测试程序测1s内处理多大数量级数据的时候，有三点需要注意： * CPU执行每条指令所需的时间实际上并不相同，例如CPU执行加法和乘法操作的耗时实际上都是不一样的。 * 现在大多计算机系统的内存管理都有缓存技术，所以频繁访问相同地址的数据和访问不相邻元素所需的时间也是不同的。 * 计算机同时运行多个程序，每个程序里还有不同的进程线程在抢占资源。 尽管有很多因素影响，但是还是可以对自己程序的运行时间有一个大体的评估的。 引用算法4里面的一段话： * 火箭科学家需要大致知道一枚试射火箭的着陆点是在大海里还是在城市中； * 医学研究者需要知道一次药物测试是会杀死还是会治愈实验对象； 所以**任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年**。 这个是最基本的，所以以上误差就不算事了。 以下以C++代码为例： 测试硬件：2015年MacPro，CPU配置：2.7 GHz Dual-Core Intel Core i5 实现三个函数，时间复杂度分别是 O(n) , O(n^2), O(nlog n)，使用加法运算来统一测试。// O(n^2)
void function2(long long n) {
long long k = 0;
for (long long i = 0; i < n; i++) {
for (long j = 0; j < n; j++) {
k++;
}
}
}
// O(nlogn)
void function3(long long n) {
long long k = 0;
for (long long i = 0; i < n; i++) {
for (long long j = 1; j < n; j = j*2) { // 注意这里j=1
k++;
}
}
}
int main() {
long long n; // 数据规模
while (1) {
cout << "输入n：";
cin >> n;
milliseconds start_time = duration_cast<milliseconds >(
system_clock::now().time_since_epoch()
);
function1(n);
// function2(n);
// function3(n);
milliseconds end_time = duration_cast<milliseconds >(
system_clock::now().time_since_epoch()
);
cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
<<" ms"<< endl;
}
}
#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace chrono;
// O(n)
void function1(long long n) {
long long k = 0;
for (long long i = 0; i < n; i++) {
k++;
}
}
// O(n^2)
void function2(long long n) {
long long k = 0;
for (long long i = 0; i < n; i++) {
for (long j = 0; j < n; j++) {
k++;
}
}
}
// O(nlogn)
void function3(long long n) {
long long k = 0;
for (long long i = 0; i < n; i++) {
for (long long j = 1; j < n; j = j*2) { // 注意这里j=1
k++;
}
}
}
int main() {
long long n; // 数据规模
while (1) {
cout << "输入n：";
cin >> n;
milliseconds start_time = duration_cast<milliseconds >(
system_clock::now().time_since_epoch()
);
function1(n);
// function2(n);
// function3(n);
milliseconds end_time = duration_cast<milliseconds >(
system_clock::now().time_since_epoch()
);
cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
<<" ms"<< endl;
}
}
