computer-science - 嵌套循环的大 O 表示法是什么，其中内循环运行固定次数而不管 N 是多少？

Question

function DoStuff(someNumber) {
    for(var i = 1; i <= someNumber; i++) {
        // some arbitrary logic
        for(var a = 0; a <= 3; a++) { // This loop gets run 4 times regardless of i
            // Do something 
        }
    }
}

此方法的 BigO 表示法是否为 O(n) + 4，因此只是 O(n)？

Answer 1

它是 O(n)，原因如下:

内部循环执行了 N 次(其中 N 是代码中的“someNumber”)。当然，它会导致 4 次处决。这并不意味着你的程序是 O(n) + 4，正如你所建议的那样(无论如何这不是大 O 符号的正确语法，你的意思是 O(n+4) 或 O(n) + O(4)) .这意味着你的程序是 O(4*n)。当一个循环嵌套在另一个循环中时，您将这些循环的两个边界相乘。也就是说，如果外循环进行到 M，内循环进行到 N，只要没有其他棘手的代码，大 O 将是 O(M*N)。所以在这种情况下，您将 n 乘以 4。

然后应用常量乘法规则。 4 是常数，所以 O(n*4) 简化为 O(n)。