ランダウの記号

計算アルゴリズムの効率を表すときに、O(n)のような表記を用いることがある。

これをO-表記と言う。
O(1)なら定数関数と呼び、一定の時間で処理が終わるアルゴリズムを意味する。
O(n)なら線形関数。処理する要素の数に比例した時間がかかる。
O(n log n)は線形対数。処理する要素の数に、その対数を取った値に比例した時間がかかる。
下に行くほど、要素数の増加が処理時間に影響を与える。
O(n^2)は二乗関数。処理する要素数の2乗に比例した時間がかかる。
O(c^n)は指数関数。要素数が増えると手に負えなくなる。いわゆる指数爆発。
O(n!)は階乗関数。指数関数よりもたちがわるい。nが100の時、つまり100の階乗は9.33262154 × 10^157

■ ランダウの記号 - Wikipedia http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7