快慢电脑运行同个O(n)程序 慢电脑初始速度是否可能更快

面试题：现有两台电脑，第一台为旧设备，RAM、ROM容量更小，处理性能更低；第二台为新设备，RAM、ROM容量更大，处理性能更高。假设两台电脑的所有进程均已停止，仅单独运行同一个时间复杂度为O(n)的程序，请问是否存在初始短时间内慢电脑的程序处理速度比快电脑更快，之后快电脑才展现出真实性能优势的可能性？如果存在请说明具体原因。

结论 #

存在这种可能性。核心原因是算法时间复杂度仅描述数据规模增长时的执行时间变化趋势，不代表小数据量下的绝对执行速度，再结合硬件、软件启动阶段的固定开销差异，就会出现初始阶段旧设备性能表现更好的情况。

具体原因 #

• 硬件唤醒与调频的开销差异：新设备的高性能核心通常搭配更激进的功耗控制策略，无负载时会进入低功耗休眠、降频状态，启动程序时需要经历核心唤醒、电压调整、频率拉升的过程，这个过程通常有几十到上百微秒的延迟；而旧设备的核心架构简单，功耗控制策略更保守，无负载时也可能维持在较高的基础频率，程序启动后可以立刻跑满性能，没有额外的唤醒等待开销。
• 小数据量下常数项的权重更高：O(n)的时间复杂度表述会忽略执行过程中的固定常数开销，仅保留和数据规模n相关的线性项。新设备的架构更复杂，程序启动阶段需要完成的虚拟地址映射、缓存预热、扩展指令集优化初始化的开销更高，在n非常小的初始阶段，常数项的开销远大于线性计算的开销，旧设备更低的固定常数开销就会表现出更快的处理速度。
• 存储初始化的响应差异：新设备常用的高端NVMe SSD虽然连续读写性能远高于旧设备的SATA SSD/机械硬盘，但部分固件的调度策略会导致小文件随机读取的初始响应延迟更高。程序启动阶段需要加载的二进制文件、依赖库多为小体积文件，旧设备反而可能更快完成加载流程。

新设备后续反超的原因 #

当程序运行一段时间、处理的数据规模n逐渐变大后，线性项的开销占比会超过固定常数项，新设备更高的IPC（每时钟周期执行指令数）、更大的缓存容量、更高的内存带宽优势会完全体现，线性计算的速度会显著超过旧设备，逐渐拉开性能差距。

内容的提问来源于stack exchange，提问作者Aryan Malik