Big-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 ++操作,以及嵌套循环中的复杂性,是否会改变其Big-O复杂性？

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

Answer 1

在第二个例子中,第一for迭代n次数,而第二迭代log2(n)时间,因为你把j通过2在每个迭代.因此,复杂度为O(n log2 n).

sum++ 在最后一行不会影响复杂性.

Answer 2

好吧，首先：Big 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(infinity)因为某些正数的除法总是大于0......或者我在这里错了？