如何通过查看 for 循环来确定 Big O 性能？

Question

我刚刚开始学习大 O 表示法，老实说我不认为我掌握了它，而且我不太确定如何通过查看 for 循环来确定 O() 性能。我列举了几个例子，然后是一些我认为正确的答案！如果它们有误，请告诉我，如有任何解释，我们将不胜感激！

for (int i = 0; i <1000; i++) {
        count ++;

我相信这会是 O(n)，因为除了恒定时间打印之外，for 循环中没有其他任何事情发生。我们迭代 'n' 次，或者在本例中为 1000?

for (int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++)
       count ++;

这个会不会有 O(n^2)，因为循环是嵌套的，它迭代 n 两次，n*n？

for (int i = 0; i < n; i++) {
    for( int j = i; j < n; j++)
       count++;

这是另一个 O(n^2) 但在最坏的情况下？或者这是 O(n log n)？

Answer 1

大 O 符号应该是帮助用户理解运行时间如何随着输入增加的指南。

对于第一个例子，无论n是什么，循环都恰好运行了1000次，因此是O(1000) = O(1)次。

对于第二个示例，嵌套循环运行 n 次，每次运行外循环，运行 n 次。这是总共 n*n = n^2 操作。因此操作次数的增加与 n 的平方成正比，因此我们说它是 O(n^2).

第三个例子，还是O(n^2)。这是因为 Big-O 表示法忽略了时间复杂度的精确公式中的常量。如果计算 j 运行的次数随着 i 的增加而增加，就会得到这种模式。

i: 0  1   2   3 ...
j: n n-1 n-2 n-3 ...

总共操作次数在1/2 n^2左右。由于 Big-O 表示法忽略常量，这仍然是 O(n^2)

How to determine Big O performance by looking at for loops?