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

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)。

他的论点是，如果< code>n是1，000，000，并且循环需要5秒，那么我的代码将需要10秒，因为它有2个for循环。这个说法之后我就糊涂了。

我从我的DSA课程中记得的是，我们在计算Big Oh时忽略了这些常数。

我错过了什么？

Answer 1

您可能会混淆时间复杂度和性能。这是两件不同（但相关）的事情。

时间复杂度涉及比较算法的增长速度，而忽略了恒定因素和混乱的现实世界条件。这些简化使其成为推理算法可扩展性的有价值的理论框架。

性能是代码在实际计算机上运行的速度。与Big O-land不同，恒定因素存在，并且通常在决定执行时间方面起主导作用。你的同事有理由承认这一点。很容易忘记O（1000000n）与大O区中的O（n）相同，但对于实际的计算机来说，常数因子是非常真实的。

Big O提供的鸟瞰图仍然很有价值；它可以帮助确定您的同事是否迷失在细节中，并寻求微观优化。

此外，您的同事认为简单的指令计数是比较这些循环安排的实际性能的一个步骤，但这仍然是一个主要的简化。考虑缓存特征;无序执行潜力;对预取、循环展开、矢量化、分支预测、寄存器分配和其他编译器优化的友好性;垃圾回收/分配开销和堆与堆栈内存访问只是几个因素，这些因素可能会在执行时间上产生巨大差异，而不仅仅是在分析中包括简单的操作。

例如，如果您的代码类似于

for (int i = 0; i < n; i++) {
    foo(arr[i]);
}

for (int i = 0; i < m; i++) {
    bar(arr[i]);
}

并且n足够大，以至于arr不能整齐地放入缓存中（也许arr的元素本身就是大的、堆分配的对象），您可能会发现第二个循环具有巨大的有害影响，因为必须将驱逐的块重新带回缓存。将其重写为

for (int i = 0, end = max(n, m); i < end; i++) {
    if (i < n) {
        foo(arr[i]);
    }

    if (i < m) {
        bar(arr[i]);
    }
}

可能会带来不成比例的效率提升，因为来自< code>arr的块只需进入缓存一次。< code>if语句可能会增加开销，但是分支预测可能会使影响可以忽略，从而避免管道刷新。

相反，如果 arr 适合缓存，则第二个循环的性能影响可以忽略不计（特别是如果 m 是有界的，更好的是，很小）。

同样，在< code>foo和< code>bar中发生的事情可能是一个关键因素。这里没有足够的信息来告诉我们，通过查看这些片段，哪个可能运行得更快，尽管它们很简单，这同样适用于问题中的片段。

在某些情况下，编译器可能有足够的信息为这两个示例生成相同的代码。

最终，解决此类争论的唯一希望是编写一个准确的基准（不一定是一件容易的事），在正常工作条件下测量代码（并不总是可能的），并根据您可能对应用程序的其他约束和指标（时间、预算、可维护性、客户需求、能源效率等）评估结果。

如果应用满足其目标或业务需求，那么讨论性能可能还为时过早。分析是确定所讨论的代码是否是问题的好方法。参见埃里克·利珀特（Eric Lippert）的《哪个更快？这为（通常）不担心这些事情提供了强有力的理由。

这是Big O的一个好处——如果两段代码只相差一个小的常量因子，那么很有可能在通过分析证明值得关注之前不值得担心。

Answer 2

在渐近表示法中，代码的时间复杂度为O(n n)= O(2n)= 1

O（n）

附带说明：
如果第一个循环需要n迭代，而第二个循环m，则时间复杂度为O（n m）。

PS：正如你提到的，我假设你的 for 循环的主体不足以影响整体复杂性。

Answer 3

是的，
复杂性理论可能有助于比较[？时间][？空格]，
但是

事实#1：O（f（N））与比较复杂性相关，在N~INFTY附近的区域，因此可以比较过程主要限制“那里”

事实2：给定N~{10k|10M|10G}，这些情况都不满足上述条件

事实#3：如果进程（算法）允许循环合并而没有任何副作用（对资源/阻塞/等）到单个传递中，则单循环处理可能始终受益于减少的循环开销。

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

因此，< br >在讨论< code>O( f( N ) )的限制之前，一定要执行一些依赖于缩放的微基准测试

一直都是。