2017-10-29 132 views
2

我无法理解为什么这段代码是为O(log 2^n)的为它的大O符号:大O符号,请解释一下O(log2n)

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

我认为这将是上)。

+2

什么部分令人困惑?注意'我=我/ 2'? –

+0

@ElliottFrisch我看到了for循环,我认为它只是0(n)。我没有在for循环中获得i = i/2的意义。我知道我被2除(它在for循环中的每个循环中是否被2除?) – sukiyo

+2

@sukiyo:它每次经过循环时都将'i'除以2,所以如果'i'开始为1024 ,那么它将是512,256,128,64,32,16,8,4,2,1,然后是0(因为整数除法),此时该循环退出。所以每当'n'加倍时,在循环退出之前你会得到更多的迭代。这就是n'的log(base 2)的定义。 – StriplingWarrior

回答

6

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

k之后次步骤假设整个事情变得1.

所以n/2^k = 1

k=log_2 n

的复杂性是O(log_2 n)

+0

是n/2^k i = i/2部分? – sukiyo

+0

@sukiyo .:是的每一步你基本上除以2你知道了 – coderredoc

+0

非常感谢你。我不明白如何写在日志形式,虽然。 n/2去哪了? – sukiyo

1

我明白了第一次错误,但看看这个,在for的每个循环中,你做了I/2,所以最后它会抛出n个log2元素。所以在最后这将是0(LOG2 N)

0

答案很简单:

由于@coderredoc解释这个代码片断是O(log n)的。对数的基数在渐近符号中是无关紧要的,因为它只会产生常数的差异。

深入的答案: 如果这是在学术语境中提出的;那么请阅读有关big-O符号和big-Θ符号之间区别的更多信息。 http://web.mit.edu/16.070/www/lecture/big_o.pdf https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation

对于您的具体问题,这是O(log n)的任何代码可以theroritically说是O(2^N)或O(N)或为O(log 2^N)。因为,大O符号描述了上限而非严格限制。