一段简单 java 代码的时间复杂度

Question

我有以下代码，我知道它的大 O 复杂度为 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 这样的二次幂。实际上，要达到 0，自 n < 2^iCount 以来，i 必须至少被 2 除 iCount=floor(log(n)+1) 次，因此 n / (2^iCount) < 1.

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

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

一段简单 java 代码的时间复杂度

Time complexity of a simple java piece of code

performance

complexity-theory

big-o

loops