algorithm - Big Oが対数であるかどうかを知る方法は？

Question

私の質問は、「BigOのわかりやすい英語の説明」という投稿から生じています。対数の複雑さの正確な意味はわかりません。時間と操作の数の間で回帰を行い、Xの二乗値を計算して、その複雑さを判断できることを私は知っています。しかし、紙の上で素早く判断する方法を知りたいです。

対数の複雑さをどのように判断しますか？良いベンチマークはありますか？

Answer 1

厳密ではありませんが、各反復で実行する必要のある作業を本質的に半分に分割するアルゴリズムがある場合、対数的に複雑になります。典型的な例は二分探索です。

Answer 2

これが意味するかどうかはわかりませんが...対数の複雑さは通常、ルートに1つのノード、2つの子、4つの孫、8を含む平衡二分木のような分散データ構造で作業しているときに発生します。曽孫など。基本的に、各レベルでノードの数に何らかの係数（2）が掛けられますが、それでも反復に関与するのはそのうちの1つだけです。または、別の例として、各ステップでインデックスが2倍になるループ：

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

そのようなものは、対数の複雑さのサインです。

Answer 3

マスター定理は通常機能します。

Answer 4

対数のBigOhについて知りたいだけの場合は、データが再発の各ステップの半分にカットされる時期に注意してください。

これは、前のステップの1/2の大きさのデータを処理している場合、それは無限の級数であるためです。

Answer 5

これは別の言い方です。

アルゴリズムが問題のサイズの桁数で線形であると仮定します。したがって、おそらく、多数を因数分解する新しいアルゴリズムがあり、桁数が線形であることを示すことができます。したがって、20桁の数値は、アルゴリズムを使用して10桁の数値の2倍の時間がかかります。これにはログが複雑になります。（そして、それは発明者にとって何か価値があるでしょう。）

二等分線も同じ動作をします。間隔の長さを1024=2 ^ 10の係数でカットするには、約10の二分ステップが必要ですが、間隔を2^20の係数でカットするのは20ステップだけです。

ログの複雑さは、アルゴリズムがすべての問題に対して高速であることを常に意味するわけではありません。O（log（n））の前の線形係数は大きくなる可能性があります。したがって、あなたのアルゴリズムは小さな問題ではひどいものになる可能性があり、問題のサイズがかなり大きくなり、他のアルゴリズムが指数関数的（または多項式）で死ぬまで役に立たなくなります。