algorithm - 时间复杂度单循环与多顺序循环

Question

今天，我和我的同事就一个特定的代码片段发生了小争执。代码看起来像这样。至少，他是这么想的。

for(int i = 0; i < n; i++) {
    // Some operations here
}

for (int i = 0; i < m; i++) { // m is always small
    // Some more operations here
}

他要我删除第二个循环，因为它会导致性能问题。

但是，我确信由于我这里没有任何嵌套循环，所以无论我放置了多少顺序循环(我们只有 2 个)，复杂度始终为 O(n) ).

他的论点是，如果 n 是 1,000,000 并且循环需要 5 秒，我的代码将需要 10 秒，因为它有 2 个 for 循环。听到这句话后我很困惑。

我从我的 DSA 类(class)中记得的是，我们在计算 Big Oh 时忽略了这些常量。

我在这里错过了什么？

Answer 1

是的，
复杂性理论可能有助于比较 [?TIME][?SPACE] 中两种不同的计算方法，
但是

不要使用[PTIME]复杂性作为低效率的论据

---

事实#1: O( f(N) ) 与N ~ INFTY 附近区域的复杂性比较相关，因此可以“在那里”比较流程主体限制

事实 #2:给定 N ~ { 10k | 10M | 10G ，不满足上述条件

事实#3:如果流程(算法)允许循环合并而没有任何副作用(对资源/阻塞/等)到一个 channel 中，单循环处理可能始终受益于减少的循环开销。

---

一个微基准将决定，而不是O( f( N ) ) for N ~ INFTY

随着许多附加效果的影响越来越大——更好或更差的缓存行对齐以及可能的 L1/L2/L3 缓存重用量，更多/更少 CPU 寄存器的智能利用——所有这些都是由可能的编译器优化，并可能进一步提高小型 N-s 的代码执行速度，超出上面的任何预期。

所以，
在诉诸争论 O( f( N ) )

的限制之前，请执行几个与缩放相关的微基准测试

总是这样。