Big Oがいつ対数であるかを知る方法？

Question

私の質問は投稿"Plain English Explanation of Big O"から発生します。私は対数的複雑さの正確な意味を知らない。私は、時間と操作数の間に回帰を行い、X二乗値を計算し、その複雑さを判断できることを知っています。しかし、私は紙の上でそれを迅速に判断する方法を知りたい。

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

Answer 1

これが意味するものなのかどうかは分かりませんが、対数複雑さは通常、ルートに1つのノード、2つの子ノード、2つの子ノードが含まれているバランス型バイナリツリーのような分散型データ構造で作業する場合に発生します。 4人の孫、8人の曾孫など基本的には各レベルでいくつかの要素（2）が乗算されますが、そのうちの1つだけが反復に含まれます。あるいは別の例として、インデックスは各ステップで倍増したループ：そのような

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

物事は対数複雑さの署名です。

Answer 2

Master theorem通常動作します。

Answer 3

厳密ではありませんが、基本的に各反復で必要な作業を半分に分けるアルゴリズムがあり、対数の複雑さがあります。古典的な例はバイナリ検索です。

Answer 4

ログオフについて知りたいのであれば、再発の各段階の半分でデータがカットされるのを目の当たりにしてください。

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

Answer 5

これは別の言い方です。

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

二重セクションは同じ振る舞いをしています。間隔の長さを1024 = 2^10の倍数にするには、約10分の2分の1ステップを要しますが、20ステップだけで、間隔は2^20分だけ短縮されます。

ログの複雑さは、必ずしもすべての問題でアルゴリズムが高速であるとは限りません。 O（log（n））の前の線形因子は大きいかもしれません。だからあなたのアルゴリズムは、小さな問題ではひどいかもしれませんし、他のアルゴリズムが指数関数的な（または多項式）死で死ぬまで問題の大きさがかなり大きくなるまで有効にならないかもしれません。