O（log n）は常にO（n）よりも速いですか

Question

異なる複雑さで同じ結果を計算する2つのalgorthimがある場合、O（log n）は常により速くなりますか？もしそうなら、説明してください。これは割り当ての問題ではありません。

Answer 1

いいえ1つのアルゴリズムがN/100で実行され、もう1つのアルゴリズムが(log N)*100で実行される場合、2番目のアルゴリズムは入力サイズが小さいほど遅くなります。漸近的複雑さは、入力サイズが無限になるまでの実行時間の振る舞いに関するものです。

Answer 2

いいえ、必ずしも高速であるとは限りません。しかし、問題のサイズが大きくなるにつれて、の最終的には、O（log n）アルゴリズムがO（n）より速い点に常に到達します。

通常、O（log n）アルゴリズムがO（n）アルゴリズムを追い越すポイントは、非常に迅速になります。 O（n）とO（n^2）の間に大きな違いがあるように、O（log n）とO（n）の間には大きな違いがあります。

あなたはジョン・ベントレーによってプログラミング真珠を読む機会を持っている場合は、そこに素晴らしい章彼はに可能なすべてをやって、O（n）のOに対するアルゴリズム（N^2）1ピットがありますO（n^2）に利点を与える。 （彼は、Alpha上でC言語でO（n^2）アルゴリズムをコーディングし、古いZ80などでは約1MHzでBASICを解釈するO（n）アルゴリズムをコーディングしています）アルゴリズムはO（n^2）を追い越します。

場合によっては、非常に複雑なアルゴリズムがありますが、複雑なアルゴリズムは、単純なものよりわずかに優れています。そのような場合、盲目的にアルゴリズムを選択しないでください。大規模な問題で高速に処理されることがあります。