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が何であるかは(あまり詳しくはないかもしれませんが)知っていますが、対数時間を持つ関数を特定する方法がわかりません。
これは単純に,この作業に必要な時間が log(n) で大きくなることを意味します(例:n = 10 では 2 秒,n = 100 では 4 秒,...).詳しくは、Wikipediaの「バイナリサーチアルゴリズム」1や「Big O記法」2の記事をご覧ください。