java - Big O Notation-请解释O(log2n)

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

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

我认为它会是 O(n)。

最佳答案

这是 O(log_2 n) 。因为它会一直运行到 n 变为 1。

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

所以n/2^k = 1k=log_2 n
复杂度是 O(log_2 n)

关于java - Big O Notation-请解释O(log2n)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46996540/