complexity-theory - 如何证明对数复杂度

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。对数复杂度。