計算量を見積もったところで、それの大きさが分からないと意味がありません。\(O(n^{100})\)と\(O(2^n)\)のどちらが大きいのでしょうか?そこで、計算量同士の比較ができるようにまとめました。本来は具体的な証明を与えなければならないのですが、大小関係がわかるようにならないと使いこなせません。どのような順序になっているのかを知って下さい。$$(ただし\(a,b\)は1より大きい実数としました。)これで先程の疑問への答えがでました。\(O(n^{100})\)と\(O(2^n)\)では、\(O(2^n)\)の方が大きくなります。疑問に思ったら、\(n\)は非常に大きい値だと仮定していることを思い出して下さい。オーダー記法は\(n\)が大きい時を考えているのでした。実感を生むために、入力サイズによる比較も行ってみましょう。入力サイズによる比較\(n\)に具体的な値を入れてみた時に、本当に先程の順序関係が成り立っているかを見てみます。(見やすさのために非常に大きい数は省略しています。...ちゃんと先程の順番通りになっていることを確認してください。今後良く出てくる大事なものは以下にまとめておきます。\(logn\)は\(n\)が大きくても非常に小さい\(nlogn\)よりも\(n^2\)のほうが大きい\(n^a\)よりも\(b^n\)のほうが大きい\(n!\)は非常に早く大きくなる(発散する)これらの計算量は、今後の基本的なアルゴリズムにおいて頻出です。大まかな大小関係だけでも抑えておくと良いでしょう。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。