[解決済み] O(n)とO(log(n))の違い -どちらが優れていて、O(log(n))とは一体何なのか？

質問

このコースはデータ構造の最初のコースで、毎回の講義やTAの講義で、次のようなことを話しています。 O(log(n)) . これは、おそらく馬鹿な質問ですが、私は誰かが正確にそれが何を意味するのか私に説明することができれば感謝します！？

どのように解決するのですか？

問題となっているもの（通常は実行時間）が、その入力サイズの対数に一致するような形でスケールすることを意味します。

ビッグ・オー表記法 を意味するものではありません。 正確 の式で表されます。 バウンド . 例えば、以下の関数の出力はすべてO(n)である。

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

xを増加させると、その出力はすべて直線的に増加するからです。 f(n) と g(n) の比率も6：1程度になる予定です。 f(10*n) と g(10*n) といった具合に。

という点については O(n) または O(log n) の方が良いと思うのですが、どうでしょうか？ n = 1000 であれば log n = 3 (log-base-10の場合)。1000秒と3秒では、どちらの方がアルゴリズムの実行に時間がかかるでしょうか？