算法复杂度与执行时间
实际测试
通过测试（代码见下文，编译指令：g++ -std=c++11 -O0 t.cpp）当代计算机耗时如下表所示，测试机器：
- Ubuntu 20
- CPU，intel i7-8750H
- Mem，16G & DDR4 & 2400MT/s
测试结果
| 执行次数 | 优化选项 | 耗时（ms） |
|---|---|---|
| 14000（数万） | -O0 | 0.771（毫秒级） |
| 14000 | -O2 | 0.613 |
| 4000000（数百万） | -O0 | 35.249（数十毫秒） |
| 4000000 | -O2 | 29.859 |
| 28000000（数千万） | -O0 | 240.723（数百毫秒） |
| 28000000 | -O2 | 197.916 |
| 196000000（数亿） | -O0 | 1686.2（秒级） |
| 196000000 | -O2 | 1410.34 |
| 8000000000（数十亿） | -O0 | 68834（数十秒级） |
| 8000000000 | -O2 | 56567.1 |
总结
不同机器执行耗时可能不同，比如嵌入式CPU对比服务器机器可能慢了几十倍，但实验结果所表现出的现象不变
竞赛时可以按照数据规模选择算法，如果数据量不大暴力法是很好的选择，简单快速
算法复杂度不能超过亿次级别，否则很容易超时，数十亿一定超时，千万级别比较保险，最好是百万级别及以下
测试代码
#include <cmath>
#include <chrono>
#include <iostream>
double cnt_g = 0;
void base_f() {
cnt_g += 3.1415926 * (std::rand() % 7);
}
long long liner_f(long long cnt) {
for(int i = 0; i < cnt; i++) base_f();
return cnt;
}
long long logn_f(long long cnt) {
int cnt_x = static_cast<long long>(std::log(cnt*1.0));
return liner_f(cnt_x);
}
long long nlogn_f(long long cnt) {
long long exe_cnt = 0;
for(int i = 0; i < cnt; i++) {
exe_cnt += logn_f(cnt);
}
return exe_cnt;
}
long long pow2_f(long long cnt){
long long exe_cnt = 0;
for(int i = 0; i < cnt; i++){
exe_cnt += liner_f(cnt);
}
return exe_cnt;
}
long long pow2logn_f(long long cnt){
long long exe_cnt = 0;
auto cnt_x = static_cast<long long>(std::log(cnt*1.0));
for(int i = 0; i < cnt_x; i++){
exe_cnt += pow2_f(cnt);
}
return exe_cnt;
}
long long pow2lognlogn_f(long long cnt){
long long exe_cnt = 0;
auto cnt_x = static_cast<long long>(std::log(cnt*1.0));
for(int i = 0; i < cnt_x; i++){
exe_cnt += pow2logn_f(cnt);
}
return exe_cnt;
}
long long cube_f(long long cnt) {
long long exe_cnt = 0;
for(int i = 0; i < cnt; i++){
exe_cnt += pow2_f(cnt);
}
return exe_cnt;
}
std::pair<long long, long long > time_stat(long long (*f)(long long ), long long cnt) {
auto res = std::pair<long long, long long>();
auto start_tp = std::chrono::steady_clock::now();
res.first = f(cnt);
auto end_tp = std::chrono::steady_clock::now();
auto span = std::chrono::duration_cast<std::chrono::microseconds>(end_tp - start_tp).count();
res.second = span;
return res;
}
void helper(const std::string& msg, long long (*f)(long long), long long cnt) {
auto res = time_stat(f, cnt);
std::cout << msg << ", cnt: " << cnt << ", exe_cnt: " << res.first
<< ", time: " << res.second/1000.0 << "ms, cnt_g: " << cnt_g << std::endl;
}
int main(int argc, char** argv) {
if(argc != 2) {
std::cerr << "ERR, please do: ./exe_able cnt" << std::endl;
return -1;
}
else {
long long cnt = std::stoll(argv[1]);
helper("logn", logn_f, cnt);
helper("n", liner_f, cnt);
helper("nlogn", nlogn_f, cnt);
helper("pow2", pow2_f, cnt);
helper("pow2logn", pow2logn_f, cnt);
helper("pow2lognlogn", pow2lognlogn_f, cnt);
helper("cube", cube_f, cnt);
}
}
输出示例
编译命令：g++ -std=c++11 -O2 test.cpp
执行命令：./a.out 2000
控制台输出：
logn, cnt: 2000, exe_cnt: 7, time: 0.034ms, cnt_g: 59.6903
n, cnt: 2000, exe_cnt: 2000, time: 0.074ms, cnt_g: 18959.5
nlogn, cnt: 2000, exe_cnt: 14000, time: 0.588ms, cnt_g: 151833
pow2, cnt: 2000, exe_cnt: 4000000, time: 29.557ms, cnt_g: 3.78582e+07
pow2logn, cnt: 2000, exe_cnt: 28000000, time: 201.471ms, cnt_g: 3.01775e+08
pow2lognlogn, cnt: 2000, exe_cnt: 196000000, time: 1409.63ms, cnt_g: 2.14893e+09
cube, cnt: 2000, exe_cnt: 8000000000, time: 57545.9ms, cnt_g: 7.7547e+10