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

log2 N未満で、n回繰り返されることがわかっています。

したがって、# iterations < log2 Nまたは# iterationsO(log N)

QED。対数の複雑さ。

Answer 2

2を掛けるNと、のサイズに関係なく、もう1回反復が追加されますN。これは、ログ関数の定義とほぼ同じです。定数を掛けるたびに、一定の量だけ増加しますN。

Answer 3

あなたのコードはまでi < N、そして各ステップで動作しi *= 2ます。ループが回実行される場合、ループは対数的複雑度を持つと言いますlog(N) + const。2 ^ log(N) = Nですので、[log(N)] + 1後回しにi > N。