简单的Java代码的时间复杂度

Question

我有以下代码，并且我知道它的复杂度为n*(log2(n))^2，但是它无法理解，但是我不明白为什么前两个循环每个都具有log2(n)的复杂度。有人可以解释我为什么吗？谢谢。

for (int i = n; i>0; i/=2) {
   for (int j = 1; j < n; j*=2) {
       for (int k = 0; k < n; k+=2) { 
              ... // constant time number of operation
        }
    }
}

Answer 1

第一循环执行O(log(n))迭代，因为i的值等于n除以​​n, n/2, n/4, n/8, .., 1之类的2的幂。实际上，要达到0，我必须自2除以​​iCount=floor(log(n)+1)后再除以n < 2^iCount倍，因此n / (2^iCount) < 1。

第二个循环执行O(log(n))迭代，因为j的值是2的幂，例如1, 2, 4, 8, 16, ...（j的最后一个可能值为2^(floor(log(n))）。

第三循环执行O(n/2)迭代，因为k的值为0, 2, 4, 6, 8, ...。