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

Answer 2

乘以N2 会增加一次迭代，无论N. 这几乎就是对数函数的定义——每次乘以N一个常数，它就会增加一个常数。

Answer 3

您的代码将一直有效i < N，并且每一步都有效i *= 2。如果您的循环运行log(N) + const时间，我们说您的循环具有对数复杂性。2 ^ log(N) = N，所以经过[log(N)] + 1几次i > N。