c++ - 斐波那契世代的渐近和实际运行时间中的常数与系统因素

Question

我实现了一个简单的 DP 方法来计算理论上在线性时间内运行的斐波那契数：

vector<ull> fib_iter(int len) {
    vector<ull> fibs = {0, 1};
    for (int i = 2; i < len; ++i){
        fibs.push_back(fibs[i-1]+fibs[i-2]);
    }
    return fibs; 
}

使用chrono库对其进行计时时，计算前 10 个需要 12.8 微秒，前 100 个需要 18.8 微秒，前 1000 个需要 63.3。我的问题是为什么这些都不比最后一个大 10 倍。这不可能是因为恒定因素，因为它们是固定的，所以一定是因为系统优化。是编译器内联、缓存、一些架构怪癖，还是就系统细节而言究竟是什么？当我递归地实现这个算法或使用矩阵求幂时，我们看不到 10 倍的跳跃，这也是同样的原因吗？

标签： c++algorithmconstantscomplexity-theoryfibonacci