時間計算量に関して - nsasakiの勉強メモ

おおざっぱに言うと、n の増大に対して計算量がどの割合で膨張するのかを示すもの。
計算式の中では一番強いものに引っ張られる。

↓は代表的なもの

名前	早さ	概要	数式	例
factorial time	slower	nのn乗に比例した時間を費やす	$n!$	巡回セールスマン問題の総当たりによる解法
指数関数時間	slow	定数のn乗に比例した時間を費やす	$k^{n}$	ルービックキューブの総当たりによる解法
多項式時間	fast	nの定数乗に比例した時間を費す	$n^{k}$	比較ソート (バブル、挿入、選択ソート)
linearithmic time	faster	多項式時間と線形時間の中間の時間を費す	$n * \log{n}$	線形対数ソート*1 (クイックソート、ヒープソート、マージソート)
線形時間	even faster	Nに直接比例した時間を費やす	$k * n$	配列走査
対数時間	much faster	Nの対数に比例した時間を費やす	$k * \log{n}$	2分探索
定数時間	fastest	入力がどんなに大きくても固定の時間を費やす	$k$	インデックスによる配列要素へのアクセス

参考:Time Complexity [C++ Reference] -- http://www.cppreference.com/wiki/complexity

たとえば、
$n! + 100^{n} + n^{200} + n\log{n} + 2n + 40\log{n} + 50$
という式があったとする。
n=1では500が圧倒的に大きい。
しかし、n = 1000　を代入すると、
$1000! \approx 1000^{1000} \times exp{-1000} \approx 10^{2700}$ *2
*3
$100^{1000} = 10^{2000}$
$1000^{200} = 10^{600}$
$1000\log{(1000)} \approx 6*10^{3}$
$2*1000 = 2*10^{3}$
$40\log{(1000)} \approx 2.4*10^{2}$
と天文学的な数字の上のほうと比べて下のほうは誤差といってもいい程度に見える。
下三つはまだ、そんなに差が出ていない。が、
これらも
n=100000000000000000000000000000000000000000000000000000000000000000
くらいを代入すれば差が開く。