オーダー記法の証明について

Question

関数 f(n) を f(n) ＝ 2 n^2 + 10n と定義する．

(1) f(n) が２次のオーダー Ｏ(n^2) であることを証明せよ．

と問題があり回答が
ある正整数以上の正整数 n で常に f(n) ≦ c n^2 となる，正実数 c を見つける．
正整数 n について常に n ≦ n^2 だから，f(n) ＝ 2 n^2 + 10n ≦ (2+10) n^2．
よって，c＝12 とおけば，n≧0 で常に f(n) ≦ c n^2．
とあるのですが、
いきなり，f(n) ＝ 2 n^2 + 10n ≦ (2+10) n^2．となる過程がよくわかりません。

Cがc＝12 とおけば，n≧0 で常に f(n) ≦ c n^2．となる意味もよくわかりません。
どなたかお教授ください

Answer 1

普通に数学の問題です。

Cを12としていますが、別に100でも問題はありません。nが自然数であるならばf(n) <= 100 * n * nですから。

この条件を満たすならばCはなんでも良いのです。そして、これ自体がオーダーの定義です。f(n)はO(n^3）でもあり、O(n^4)でもあります。

Comments

[BitCoin]

Cの意味が分かりました。ありがとうございます

Answer 2

コメント

関数 f(n)は正の整数nに対して定義されてるんですかね。もし正の実数に対して定義されているのであれば、nを正整数と置いているその回答はマズいっすね。

---

回答

10 n ≦ 10 n^2の両辺に2 n^2を足すと

2 n^2 + 10 n ≦ 2 n^2 + 10 n^2 = (10 + 2) n ^2

左辺はf(n)そのものなので、正整数nに対して、

f(n) ≦ (10+2) n^2 = 12 n^2

が成り立つ。

Cがc＝12 とおけば，n≧0 で常に f(n) ≦ c n^2．となる意味もよくわかりません。

これはオーダーの定義に立ち返りませう。

Comments

[BitCoin]

うまいことf(n)=<12n^2としたわけですね
分かりやすかったです、冒頭でおっしゃった
もし正の実数に対して定義されているのであれば、nを正整数と置いているその回答はマズいっすね。
これはどういうことでしょうか？

[tachikoma]

n=1,2...等の正の整数については上から押さえられることを示していますが、n=1.2, √2, ...などの実数に対してC n^2で上から押さえられることを証明していません。オーダーの定義から、もし仮に関数f(n)が実数で定義されていれば、ある実数Nよりも大きな全てのnについて上から押さえられることを示さなくてはなりません。もっとも、この場合証明の中にある"正整数n"を”正実数n"と書き換えれば済む話ですが。

[BitCoin]

なるほど、正整数なら１２ですが正実数ならCがどのような数になればいいのでしょうか？

[tachikoma]

cは正実数 c としているので、12以上の実数ならokですよ。

[BitCoin]

ありがとうございます

Answer 3

いきなり，f(n) ＝ 2 n^2 + 10n ≦ (2+10) n^2．となる過程がよくわかりません。

すでに上で示してあるように正整数 n について常に n ≦ n^2 だから、2 n^2 + 10n ≦ 2 n^2 + 10n^2 = 12n^2です。

Comments

[BitCoin]

なるほど、2 n^2 + 10n ≦ (2+10) n^2の過程は分かりました。
問題の定数Cなのですが
この証明はいってみればべき乗数が一番大きいもの以外は無視していいことを証明しろということですよね？
n ≦ n^2 をつかい2 n^2 + 10n ≦ (2+10) n^2となりC=12となるのはわかったのですが
Cがなぜでできたのか？正実数 cを見つければ証明可能なのがよくわかりません。　なぜですか？