計算量同士の比較と入力サイズによる比較

2019年11月20日アルゴリズム概要入門

計算量同士の比較

計算量を見積もったところで、それの大きさが分からないと意味がありません。例えば、\(O(n^{100})\) と \(O(2^n)\) のどちらが大きいのでしょうか?

そこで、計算量同士の比較ができるようにまとめました。本来は具体的な証明を与えなければならないのですが、数学的に詳しい話はここでは割愛します。

大小関係がわかるようにならないと使いこなせません。まずはどのような順序になっているのかを知って下さい。

$$\log n < \sqrt{n} < n < n\log n < n^a < b^n < n! $$

(ただし \(a,b\) は1より大きい実数とします)

これで先程の疑問への答えがでました。\(O(n^{100})\) と \(O(2^n)\) では、\(O(2^n)\) の方が大きくなります。

もし疑問に思ったら、\(n\) は非常に大きい値だと仮定していることを思い出して下さい。オーダー記法は \(n\) が非常に大きい時を考えているのでした。

もう少し実感を生むために、入力サイズによる比較も行ってみましょう。

入力サイズによる比較

\(n\) に具体的な値を入れてみた時に、本当に先程の順序関係が成り立っているかを見てみます。(見やすさのために非常に大きい数は省略し、小数も丸めています。)

\(logn\)\(\sqrt(n)\)\(n\)\(nlogn\)\(n^2\)\(2^n\)\(n!\)
12582532120
23102310010243628800
2420594001048576
37501952500
41010046010000
631100069071000000
91001000092103100000000
113161000001151292

ちゃんと先程の順番通りになっていることを確認してください。今後良く出てくる大事なものは以下にまとめておきます。

  • \(logn\) は \(n\) が大きくても非常に小さい
  • \(nlogn\) よりも \(n^2\) のほうが大きい
  • \(n^a\) よりも \(b^n\) のほうが大きい(\(n^2\) よりも \(2^n\) のほうが大きい)
  • \(n!\) は非常に早く大きくなる(発散する)

これらの計算量は、今後の基本的なアルゴリズムにおいて頻出です。大まかな大小関係だけでも抑えておくと良いでしょう。