这个算法的Big O复杂度是多少

Question

我似乎无法计算出该算法的时间复杂度。我知道 while 循环将执行 O(log n) 次，因为 n 一直减半。但我不太确定如何表示内部 for 循环的时间复杂度。

while(n>0){
   for(int j = 0; j < n; j++){
        System.out.println("*");
   }
   n = n/2;
}

Answer 1

我们可以通过检查找出两个循环的复杂度。对于 n = 8 的输入，内部循环将在每次迭代中打印出这么多的星星：

8 + 4 + 2 + 1 = 15 ~ 2^4

对于 n = 16:

16 + 8 + 4 + 2 + 1 = 31 ~ 2^5

这里的复杂度是：

O(2^([log_2(N)]+1)) = 2*O(2^log_2[N])
                    = O(N)

我们可以看到，在每一步打印语句的数量大约是输入值 N 的两倍。所以打印操作的总数实际上是O(N)，与输入的实际值N.

成线性关系

Answer 2

设 n₀ 为 n 的起始值。
在 while 循环的 i-th（从 0）迭代处，n = n₀ * ½ⁱ
while 循环一次迭代的成本是 n（因为 for 循环）

因此全局成本是：i 从 0 到 n₀ * ½ⁱ
的总和或者：n₀ 乘以 i 从 0 到 ½ⁱ

的总和

因此全局成本是 O(2.n₀) 或 O(n₀)

Answer 3

每个 while 循环将 n 除以 2。

因此，第一个for循环会运行 n次，第二个for循环会运行 n/2次，第三个for循环会运行 ] n/4次，以此类推。

如果我们将n设置为任意大的值，那么复杂度为：

n + n/2 + n/4 + n/8 + n/16 + n/32 + ... = 2n

当然，n 是一个整数，以编程方式，经过足够多的重复后，除法会得到 0。

因此，算法的time-complexity将是O(2N) = O(N)

What is the Big O complexity of this algorithm