2 
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)？

4

3 回答 3

3

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

于 2013-04-25T01:11:38.707 回答
1

是的，O(4*n)就是 ，与 相同O(n)。你可以这样想：由于循环重复了固定的次数，你可以像这样“展开”它：

for(var i = 1; i <= someNumber; i++) {
    // some arbitrary logic
    // Do something
    // Do something
    // Do something
    // Do something
}

这绝对是O(n)。

于 2013-04-25T01:05:55.623 回答
1

该算法确实在 O(n) 时间内运行，但您的分析是错误的。如果你使用那些嵌套循环，你会意识到

  • 内循环总是运行固定次数，因此每次执行内循环时，它都会执行 O(1) 的工作。

  • 外循环执行 O(n) 次。每次迭代都会做一些恒定的工作，加上运行内部循环所需的工作。因此，每次迭代都会做 O(1) 的工作。因此，运行循环嵌套所需的总工作量为 O(n)。

请注意，您不要将两者加在一起 ​​- 说因为内部循环运行 4 次而外部循环运行 O(n) 次，所以工作是 O(n) + 4 = O(n) 是不正确的. 相反，您必须将它们相乘。结果是相同的答案，但这并不意味着该方法是正确的。例如，如果内部循环也运行了 n 次，那么您的分析会错误地指出运行时间是 O(n) + O(n) = O(n)，而实际上运行时间是 O(n) × O (n) = O(n 2 )。

希望这可以帮助！

于 2013-04-25T01:06:24.527 回答