时间复杂度对数

Question

for(i = 1; i < n; i *= 2) {
    sum++;
    for(j = 0; j < n; j += 2)
        total++;
}

时间复杂度：

O(log(n))
O(log(n))
O(n)*O(log(n))
O(n)*O(log(n))

所以最后的答案是：O(log(n))

这是正确的吗？

Answer 1

复杂度是这样的：

O(lgN)
    O(1)
    O(N/2) == O(N)
         O(1)

所以复杂度是：

this is the final answer O(lgN)*(O(1) + O(N)*O(1))

O(N)*O(1) = O(N) (1)

O(N)+O(1) = O(N) (2) because O(N) is bigger than O(1)

assuming (1) & (2) the final answer will be O(lgN)*O(N) = O(N lgN)

Answer 2

复杂度为：O(n) * O(lg(n))

时间复杂度对数

Time complexity logarithmic

java

time

complexity-theory

structure