时间复杂度单循环与多个顺序循环 [英] Time Complexity single loop vs multiple sequential loops

问题描述

今天，我和我的同事对一个特定的代码片段有一个小争论.该代码看起来像这样.至少，这就是他的想象.

Today, me and my colleague had a small argument about one particular code snippet. The code looks something like this. At least, this is what he imagined it to be.

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
}

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

He wanted me to remove the second loop, since it would cause performance issues.

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

However, I was sure that since I don't have any nested loops here, the complexity will always be O(n), no matter how many sequential loops I put (only 2 we had).

他的论据是，如果 n 为1,000,000，并且循环需要5秒钟，那么我的代码将花费10秒，因为它有2个for循环.这句话使我感到困惑.

His argument was that if n is 1,000,000 and the loop takes 5 seconds, my code will take 10 seconds, since it has 2 for loops. I was confused after this statement.

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

What I remember from my DSA lessons is that we ignore such constants while calculating Big Oh.

我在这里想念什么?

推荐答案

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

事实1: O(f(N)) 与比较复杂性有关，在靠近 N〜INFTY的区域，因此可以在那里"比较流程的主要限制

Fact #1: O( f(N) ) is relevant for comparing complexities, in areas near N ~ INFTY, so the process principal limits are being possible to be compared "there"

事实2:给出了 N〜{10k |10M |10G} ，所有这些情况都不符合上述条件

Fact #2: Given N ~ { 10k | 10M | 10G }, none of such cases meets the above cited condition

事实#3::如果进程(算法)允许将循环合并而没有任何副作用(对资源/阻塞等)，则单循环处理可能总是从减少的循环开销中受益.

Fact #3: If the process ( algorithm ) allows the loops to get merged without any side-effects ( on resources / blocking / etc ) into a single pass, the single-loop processing may always benefit from the reduced looping overheads.

由于许多其他影响会产生更强的影响力-更好或更糟糕的缓存行对齐以及可能的L1/L2/L3缓存重用的数量，智能利用更多/更少的CPU寄存器-所有这些均由以下因素驱动可能的编译器优化，并可能进一步提高小型 N -s的代码执行速度，超出了上面的预期.

as many additional effects get stronger influence - better or poor cache-line alignment and the amount of possible L1/L2/L3-cache re-uses, smart harnessing of more / less CPU-registers - all of which is driven by possible compiler-optimisations and may further increase code-execution speeds for small N-s, beyond any expectations from above.

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

始终如此.

这篇关于时间复杂度单循环与多个顺序循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！