O(log n)とは具体的にどのような意味ですか？

Big O Notationの実行時間と償却時間について学んでいます。 入力の大きさがアルゴリズムの成長に比例して影響を与えるという意味で、O(n)線形時間という概念を理解しています...同様に、例えば2次時間O(n2)なども理解しています...順列生成器のように、階乗によって成長するO(n!)時間を持つアルゴリズムもあります。

例えば、次のような関数は、アルゴリズムが入力nに比例して成長するため、O(n)となります。

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

同様に、入れ子のループがあった場合、時間はO(n2)となります。

しかし、O(log n)とは一体何でしょうか？ 例えば、完全な二分木の高さがO(log n)であるというのはどういうことでしょうか？

log10100 = 2という意味で、Logarithmが何であるかは（あまり詳しくはないかもしれませんが）知っていますが、対数時間を持つ関数を特定する方法がわかりません。

Flimzy
編集された質問 15日 7月 2019 в 8:29
プログラミング
time-complexity big-o
21日 2月 2010 в 8:05
40 ビュー

対数実行時間（O(log n)）とは、基本的に入力サイズの対数に比例して実行時間が長くなることを意味します。例えば、10個のアイテムに最大でもxの時間がかかり、100個のアイテムに最大でも2x、10,000個のアイテムに最大でも4xの時間がかかるとすると、O(log n)の時間的複雑さになると考えてよいでしょう。

Anon.
編集した答え 21日 2月 2010 в 8:27
解説 (10)

これは単純に，この作業に必要な時間が log(n) で大きくなることを意味します（例：n = 10 では 2 秒，n = 100 では 4 秒，...）．詳しくは、Wikipediaの「バイナリサーチアルゴリズム」1や「Big O記法」2の記事をご覧ください。

解説 (0)

完全なバイナリの例では、検索が次のようになるため、O(ln n)となります。

1 2 3 4 5 6 7 8 9 10 11 12

4を検索すると3件ヒットします。6, 3, 4 となります。そしてlog2 12 = 3、これは必要とされるヒット数の目安になります。

解説 (2)