純C/C++ O(n)的算法居然超時了(>1sec)，此時的n究竟是多大？

資料來源:https://mp.weixin.qq.com/s/xZ7hVMk_xLCeiIEgZiFVdA

線上編譯器: https://www.tutorialspoint.com/compile_c_online.php

計算機的運算速度主要看CPU的配置，以2015年MacPro為例，CPU配置：2.7 GHz Dual-Core Intel Core i5 。

code:

#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;
    }
}

心得:

    這比『SQL 運行 多久 時間 建議 極限/上限/最長/最大 用戶體驗 / 響應時間 3秒(3s)=客戶端UI渲染耗時+網絡請求耗時+應用程序處理耗時+查詢數據庫耗時，0.5秒就是留給數據庫1/6的處理時間。』還要寬鬆