该算法的 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

每个 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。

因此，算法的时间复杂度为O(2N)=O(N)