大O复杂度Java

Question

我是新手学习Java，我的问题与大O复杂度有关。

对于a），一个嵌套循环显然是O(n^2)。

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

然而，对于 b)，在结尾进行 sum++ 操作，并且在嵌套循环中存在复杂情况，这是否会改变其大O复杂度呢？

int sum = 0;
for ( int i = 1; i <= n; i++)
    for ( int j = n; j > 0; j /= 2)
        sum++;

- Katherine

---

顺便提一下，也可以查看这个链接：https://dev59.com/enVD5IYBdhLWcg3wXaYd - Rahul Tripathi

循环内的那些常数时间操作会对估计中被忽略的项做出贡献。 - ChiefTwoPencils

请注意，除非您有一个隐藏的昂贵操作（例如对LinkedList上的get()），这是由于库的无效假设而导致的，否则语言对于大O分析来说是无关紧要的。 - chrylis -cautiouslyoptimistic-

只是一点提示：这不仅与Java有关，而且与算法本身有关，因此它是语言无关的。所有常数时间操作的复杂度都为O(1)。 - Nitin Dandriyal

你应该问自己的是，对于给定的 n 值，内部循环会运行多少次。你可以看到，如果 n = 10，它将运行 4 次；对于 n = 100，它将运行 7 次；对于 n = 1000，它将运行 10 次。所以你可以看到这已经不是线性的了。然后你可以使用一些数学代数进行正式证明，但你已经知道它不应该是什么（比如 O(n^2)）。 - Alexis C.

Answer 1

在你的第二个例子中，第一个for循环迭代n次，而第二个循环迭代log2(n)次，因为你在每次迭代中将j除以2。因此，复杂度为O(n log2 n)。

最后一行的sum++对复杂度没有影响。

- ntalbs

Answer 2

显然，在你的例子中b)，内部循环的迭代次数比a)少。每次迭代将迭代计数器减半，本质上是对数(log2)操作，因此例子b)的O复杂度为O(n log2(n))。

请注意，这不仅适用于Java - 在任何其他语言中都是一样的 :-)

干杯，

- Anders R. Bystrup

Answer 3

首先，大O标记与编程语言无关，它仅取决于实现。因此，使用Java或任何其他语言执行循环是无关紧要的（除了解释器/编译器执行的一些优化，这将改变程序流程）。

对于嵌套循环：

1) sum++被视为常数操作，成本为1。因此可以忽略它。 O(n * 1) = O(n)

2) 外部循环基本保持不变，具有O(n-1)，相当于O(n)，因为在渐近计算中始终可以忽略常数项。

3) 内部循环需要log2(n)步骤才能完成。在每个步骤中，n会减半，因此乘以2会回到一步，这导致二进制对数。

总之，复杂度为O(n log2(n))

编辑：有趣的事情是，到目前为止没有人注意到内部循环的实际复杂度为O(无穷大)，因为某个正数的除法总是大于0... 或者我在这里错了吗？

- gapvision

---

嗨，你是怎么确定内部循环需要log2(n)的？ - Katherine

如果您查看循环，步骤是j，j/2，j/4，j/8...反向时，您需要将每个步骤乘以2才能到达下一个步骤。 最多可能需要n步，这将导致反向方向为2^n。要回到我们的原始循环，我们需要取指数函数的反函数，即对数... - gapvision

谢谢！ :) 还有一个问题，当外层循环如下所示时会发生什么：for (int i = 1; i <= n * n; i++)，这是否会使其成为O(n^2)，因为i<n*n？ - Katherine

是的，O(n^2)将是外部循环的复杂度。 - gapvision

Answer 4

从纯计算机科学的角度来看，大O（见定义）描述了最坏情况。这甚至意味着如果你减少内部循环的次数，O（n ^ 2）仍然适用。但是，您可以将其编写为一个不太上升的函数。

- Radovan