アルゴリズム オーダー記法 定数の求め方

初めて質問します。
アルゴリズムのオーダー記法の問題で（言語はjavaです）、
3n^2+2^nがO(n^2)であることを示せ。また定数cと自然数mの値を求めよ。
という例題を解いています。回答には、

n>=8のとき、3n^2+2^n<=2^n+2^n=2x(2^n). よってc=2, m=8

とありますが、どうしてn>=8のときなのか、その理由がわかりません。
また、2^n+2^nなのですが、3n^2より2^nのほうが大きいため、3n^2を2^nに変更して定数を求めるという考えてあっておりますでしょうか。テキストがすべて英語のため、訳が間違っているかもしれませんが、アルゴリズムに詳しい方どうかよろしくお願いいたします。

No.1 ベストアンサー 回答者： kmee 回答日時： 2017/04/02 10:24

> 3n^2+2^nがO(n^2)であることを示せ

O(2^n)では?

> どうしてn>=8のときなのか

オーダー記法は、n→∞のときのことを表わします。
そのため、n→∞で無視できるようなもの(定数等)が、nが小さいときには無視できないことがあります。
この問題でも、 n<8 のときには 3n^2>2^n なので、ここだけ見たら O(2^n) とはなりません。

余談:
クイックソート等はO(n・log n)で、O(n^2)のソートより速い、ということになっています。
ですが、nが小さい場合は、オーダー表記に出てこない部分の影響が大きく出るため、O(n・log n)の方がO(n^2)より遅い、ということがあります。


> 3n^2より2^nのほうが大きいため、3n^2を2^nに変更して定数を求めるという考えてあっておりますでしょうか。

オーダーの定義を確認してください。
{f(x){ < M・|g(x)|
のとき
f(x)=O(g(x))
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3 …

作業として、一番大きい項から云々もありますが、厳密にやるなら、上記の定義が成り立つかどうか調べるこになります。


c,m については、説明が無いので、わかりません。

この回答へのお礼

kmee様、
早速のご返答ありがとうございます。また説明不足やタイポ等、申し訳ありませんでした。おっしゃる通り、O(2^n)です。
c, mにつきましては、「整数mと正の定数cが存在して、n>=mである任意のnについて、f(n)<=c*g(n)であること」の意味でのcとmでした。
定義自体はなんとかわかりかけてきました。n>=8についても理解できました。しかしどのようにn>=8という数字が導き出せるのかがわかりませんが、グラフのサイトを使ってみたところ、3n^と2^nの二つのグラフの交点がn=7.33になったので、n>=8になるのだろうと今は理解しております。教えていただいたサイトを何回も読み、理解できるまであきらめず頑張ります。
ありがとうございました。

お礼日時：2017/04/03 14:10