此嵌套循环的时间复杂度

Question

这段代码的时间复杂度是多少？ nlgn 或 nlgn^2

for (int i = 1; i <= n ; i*=2 ) {
        for (int j = 1; j <= n ; j*=2 ) {
            for (int k = 0; k <= j ; k++) {
                x++; 
                      }}}

Answer 1

首先 for takes log n time (exponential growth)

第二个 for 循环也需要 log n 时间(exponential growth)

第三个需要n次(linear growth)

所以总时间 = 乘以所有，我们得到

log n * log n * n

所以时间复杂度是

O(n (logn)^2)

Answer 2

时间复杂度为 n*((logn)^2) 因为第一个循环运行 logn 次，第二个循环运行 logn 次，第三个循环将运行 n 次，因为它将是 gp 1+2+4+8 的总和。所以答案是 n*(logn)*(logn)

此嵌套循环的时间复杂度

Time Complexity of this nested loops

time

big-o

time-complexity