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

アルゴリズム概要入門

計算量同士の比較

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

そこで、計算量同士の比較ができるようにまとめました。本来は具体的な証明を与えなければならないのですが、大小関係がわかるようにならないと使いこなせません。まずはどのような順序になっているのかを知って下さい。

$$logn < \sqrt{n} < n < nlogn < 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!\)は非常に早く大きくなる(発散する)

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

アルゴリズム概要入門

Posted by cs-learner