java - 我怎么会误解这些 Java 函数的 Big-O？

Question

对于第一个例子，结果是:O(n)，虽然不知道为什么。

示例 1:

for (k = 0; k <= n / 8; k++) // will be O(n/8) thus, O(n)
     System.out.println(k); // will be O(n)
System.out.println("Hello World!"); // will be O(1) because not in a loop
for (p = n; p >= 1; p--) // will be O(n-1) thus, O(n) 
     System.out.print(p % 2); // not sure what % will do here, but I think it's still O(n)
     // Overall I think it's O(n)

对于第二个例子。结果是 O(n^2)，不知道为什么。

例子2:

for (k = 0; k < n - 1; k++) // will be O(n-1) or O(n)
     for (m = k + 1; m < n; m++) // will be O(n^2) because nested loop
        System.out.println(k * m); // not sure what this will do but I think it will be O(n^2)
     // Overall I think it's O(n^2)
 
 

对于第三个例子，结果是 O(n)，但不确定为什么。

示例 3:

for (i = n - 3; i <= n - 1; i++) { // not sure here, maybe O(n-1), thus O(n)
     System.out.println(i); // since it is nested then O(n)
     for (k = 1; k <= n; k++) // since this is the second loop, then O(n^2)
        System.out.println(i + k); // not sure what this will do, but I think it will be O(n^2)
} // Overall I think it's O(n^2)
 

 

最后的例子结果是O(n^2)，也不知道为什么。

例子4:

for (a = 1; a <= n / 3; a++) // will be O(n/3) thus O(n)
     for (b = 1; b <= 2 * n; b++) // since it's a nested loop it will be O(2n^2) thus O(n^2)
        System.out.println(a * b); // not sure what this will do, but I think it will be O(n^2)
     // Overall I think it's O(n^2)

有人可以通读这些并解释我做错了什么吗？我的理由是我们跟踪“n”变量，因为这是用户输入的内容，我们会看到它是如何增长的。如果它是单个语句，则为常数时间 O(1)，如果它在循环中，则默认为 O(n)，如果它在嵌套循环中，则为 O(n^2)。

Answer 1

由于您在示例 1、2 和 4 中的猜测等于您的解决方案，我假设您只有示例 3 有问题。

当您仔细查看第一行时 for (i = n - 3; i <= n - 1; i++) , 你会看到它来自 n-3至 n-1 (含)，因此它不依赖于 n 的值.

for (i = n - 3; i <= n - 1; i++) { // O(3), so O(1) (since it'a a constant factor)
    System.out.println(i); // nested, O(1)
    for (k = 1; k <= n; k++) // O(n)
        System.out.println(i + k); // nested, so O(n)
} // Overall O(n)