LeetCode 238题性能差异：双循环代码耗时2ms，三循环仅1ms

虽然两段代码的时间复杂度都是O(n)，但常数因子的细节差异会直接导致实际运行时间拉开差距，具体原因如下：

• 乘法操作次数的差异
  你的双循环实现（代码片段1）：

  • 第一个循环执行n-1次两数乘法；
  • 第二个循环每次迭代要做2次乘法（三数相乘）加1次乘法（更新product），共3*(n-1)次乘法；
  • 总乘法次数为4n-4次。

  三循环实现（代码片段2）：

  • 第一个for-each循环是无效操作：修改的是循环变量的副本，不会改变原数组，编译器会直接优化掉这个循环；
  • 前缀循环执行n次两数乘法；
  • 后缀循环每次迭代执行2次两数乘法，共2n次；
  • 总乘法次数为3n次。
    乘法是相对耗时的CPU指令，更少的乘法操作自然会带来更快的执行速度。

• 指令复杂度与编译器优化空间
  代码片段1的第二个循环包含复合的三数乘法赋值，CPU需要更多指令周期完成；而代码片段2的操作都是简单的两数相乘或赋值，逻辑更直白，编译器更容易做循环展开、指令重排等优化，进一步提升执行效率。

• 数据依赖与CPU流水线利用率
  代码片段1的第二个循环中，每次操作需要同时读取多个变量且存在数据依赖，可能导致CPU流水线停顿；而代码片段2的前缀、后缀循环都是单向依赖（前缀仅依赖前一个prefix值，后缀仅依赖前一个postfix值），流水线的利用率更高。

总结：时间复杂度只描述算法的渐近增长趋势，实际运行速度还取决于循环内的操作数量、指令复杂度、编译器优化等常数因子，这些细节的差异会让同样O(n)的代码出现明显耗时差距。

内容的提问来源于stack exchange，提问作者Vinay Soni