使用 Java 算法的最坏情况大 O

Question

1.

for(i = 0; i < 3; i++){
    for(j = 0; j < 10; j++){
        print i+j;
    }
}

我假设 Big O 是 30，因为最多的次数是 3*10。

2.

for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
        print i+j;
    }
}

O 会是 n*m 吗？

3.

for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
        for(int k = 1; k < 1000; k *= 2){
            print i+j+k;
        }
    }
}

n * m * log base 2 (1000) 大O在nlog(n)次

4.

for(i = 0; i < n - 10; i++){
    for(j = 0; j < m/2; j++){
        print i+j;
    }
}

5.

for(i = 0; i < n; i++){
   print i;
}
//n and m are some integers
for(j = 1; j < m; j *= 2){
   print j;
}

如果你认识 Big O，有人可以帮我解决这个问题吗？我正在看这些，不知所措。我希望我将其发布在正确的位置，我发现这些问题很困难。我感谢任何帮助。

Answer 1

任何常数因子都可以忽略。 O(30) 等于 O(1)，这是人们通常所说的 1).

2) 就是这样。

3) 在O(n*m*log_2(1000))中，log_2(1000)是常量，所以是O(n*m).

4) O(n-10) 等同于 O(n)。 O(m/2) 与 O(m) 相同。于是，又是O(n*m)。

5) 平凡 O(n).

6) O(log_2(m)).

Answer 2

我认为重要的是要指出 Big O 表示法是关于函数的，给定一个任意常数，在某些时候将被视为上限。

O(1)

这是因为每个循环都在 固定的时间 中迭代。我们将其称为 O(1) 而不是 O(30)，因为作为上限的函数是 1，具有任意常数 >=30.
O(n*m)

只是因为我们必须循环 m 次迭代 n 次。
O(n*m)

这与上一个相同，只是我们在中间加入了另一个循环。现在你可以注意到这个循环与第一个问题类似，只是一个常数时间。因此，您甚至不需要真正花时间弄清楚它循环的频率，因为它始终是常数——它是 O(1) 并且会被解释为 O(n*m*1) 我们可以简单地称之为 O (n*m)
O(n*m)

对于外部循环，不要陷入 .. - 10 并意识到我们可以说循环在 O(n) 中运行。我们可以忽略 .. - 10 ，原因与我们在第一个问题中忽略确切值的原因相同； 常数并不重要。同样的原则也适用于 m/2，因为你可以认为 m 只是被一个常量 1/2 操纵。所以我们可以称之为 O(n*m).
T(n) = O(n) + O(lg m) => O(n + lg m)

所以我们必须在这里查看两个组件；第一个循环和第二个循环。第一个循环显然是 O(n)，所以这没问题。现在第二个循环有点棘手。基本上，您可以注意到迭代器 j 呈指数增长（特别是 2 的幂），因此该循环将是运行指数（对数）的倒数。所以这个函数运行时间为 O(n + lg m).

Worst Case Big O with Java Algorithms