計算量同士の比較と入力サイズによる比較
Contents
計算量同士の比較
計算量を見積もったところで、それの大きさが分からないと意味がありません。例えば、\(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!\) |
| 1 | 2 | 5 | 8 | 25 | 32 | 120 |
| 2 | 3 | 10 | 23 | 100 | 1024 | 3628800 |
| 2 | 4 | 20 | 59 | 400 | 1048576 | … |
| 3 | 7 | 50 | 195 | 2500 | … | |
| 4 | 10 | 100 | 460 | 10000 | ||
| 6 | 31 | 1000 | 6907 | 1000000 | ||
| 9 | 100 | 10000 | 92103 | 100000000 | ||
| 11 | 316 | 100000 | 1151292 | … |
ちゃんと先程の順番通りになっていることを確認してください。今後良く出てくる大事なものは以下にまとめておきます。
- \(logn\) は \(n\) が大きくても非常に小さい
- \(nlogn\) よりも \(n^2\) のほうが大きい
- \(n^a\) よりも \(b^n\) のほうが大きい（\(n^2\) よりも \(2^n\) のほうが大きい）
- \(n!\) は非常に早く大きくなる（発散する）
これらの計算量は、今後の基本的なアルゴリズムにおいて頻出です。大まかな大小関係だけでも抑えておくと良いでしょう。