如何证明对数复杂度

Question

for (int i = 1; i < N; i *= 2) { ... }

这样的事情是对数复杂性的签名.

但是如何得到log(N)？

你能提供数学证据吗？

Answer 1

关于算法复杂性的有用参考:http://en.wikipedia.org/wiki/Big_O_notation

在第n次迭代中,

i = 2^n

我们知道它会迭代到 i >= N

因此,

i < N 

现在,

2^n = i < N

N > 2^n

log2 N > log2 (2^n)

log2 N > n

我们知道它迭代n次,小于log2 N.

因此# iterations < log2 N,或者# iterations是O(log N)

QED.对数复杂度.