Linux Shell下time命令测算算法时间复杂度结果不符预期

• 大O复杂度本身是输入规模n趋向无穷大时的渐近增长度量，推导过程会直接丢弃常数系数、低阶计算项、程序启动/内存初始化等固定开销。如果测试选取的输入规模不够大，耗时构成还没进入最高阶项主导的区间，低阶项、固定开销的占比会远高于高阶项，实际增长幅度自然和纯高阶幂次的理论预期存在偏差。
• 你使用的Linux Shell time 命令统计的是进程级的总资源占用，并非算法逻辑本身的纯计算耗时：统计结果会混入操作系统进程调度、CPU上下文切换、内存缺页中断、后台服务抢占资源、IO等待等系统级开销。如果单次算法运行的绝对耗时较短，这些测量噪声的占比足以完全掩盖算法本身的耗时增长规律。
• 理论复杂度推导默认所有基本操作的执行代价为固定常数，这个假设在真实硬件上不成立：CPU缓存命中率、分支预测成功率、编译器自动优化（循环展开、SIMD向量化等）、访存地址连续性都会带来数倍到上百倍的单步操作效率差。哪怕是更高阶的O(n⁵)算法，如果访存模式连续、缓存命中率远高于O(n³)的实现，在中小输入规模下的实际耗时增长完全可能比理论预期平缓很多；反过来如果算法运行时触发了磁盘Swap交换、频繁缓存行失效，耗时也可能比理论预期出现跳崖式陡增。
• 理论复杂度推导可能存在疏漏：人工推导时很容易忽略代码中的隐式循环、特殊分支带来的实际执行次数变化，或是误判了内置数据结构、标准库函数的自身复杂度，导致你认定的O(n³)、O(n⁵)和代码实际的运行复杂度不匹配。

内容的提问来源于stack exchange，提问作者Lorenzo Bernardini