大O表示法 - 请解释O(log2n)

Question

我无法理解为什么这段代码的O(log 2 ^ n)为其Big O表示法:

for (int i = n; i>=1; i=i/2){
    sum = i+j;
}

我以为它会是O(n).

Answer 1

这是O(log_2 n).因为它会一直运行到n1.

在第k步之后假设整个事情变成1.

所以 n/2^k = 1

k=log_2 n

复杂性是 O(log_2 n)