━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題２
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (関数のオーダー)

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

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

(2) f(n) が3次以下のオーダー Ｏ(n^3) であるかどうかを答えよ (証明は不要)．

(3) f(n) が1次(線形)以下のオーダー Ｏ(n) ではないことを証明せよ．

──────────────────────────────────────

●答 (関数のオーダー)

(1) ある正整数以上の正整数 n で常に f(n) ≦ c n^2 となる，正実数 c を見つける．
正整数 n について常に n ≦ n^2 だから，f(n) ＝ 2 n^2 + 10n ≦ (2+10) n^2．
よって，c＝12 とおけば，n≧1 のとき常に f(n) ≦ c n^2．

(2) Ｏ(n^3) である．

(3) f(n) が Ｏ(n) であると仮定して，矛盾を導く．この仮定と Ｏ記法の定義より，
正実数 c が存在し，ある正整数 m 以上の正整数 n について常に f(n) ≦ cn．
ここで，f(n) ≦ cn  ⇔  2 n^2 + 10n ≦ cn  ⇔  n (n-(c/2-5)) ≦ 0．
n ＝ max(m, [c/2-5]+1) のとき，n は m 以上の正整数なので，不等式
n (n - (c/2-5)) ≦ 0 が成り立つ．一方，n の定め方より，n と n-(c/2-5) は共に
正なのでその積 n (n-(c/2-5)) も正であり，この不等式に矛盾する．

※ここで，[x] は x 以上の最小の整数を表す．

[解説]

(1) c の値は，主要項の係数を超える実数を任意に選べばよい．
上記の解答では係数の和である 12 を選んだが，他の c の値も選べる．
例えば，主要項が 2 n^2 なので，c として係数 2 を超える 3 を選べば，
f(n) ≦ c n^2  ⇔  2 n^2 + 10n ≦ 3 n^2  ⇔  n(n-10) ≧ 0 だから，
n≧10 で常に f(n) ≦ c n^2 が成り立つ．

(2) 証明は (1) と同様．「任意の自然数 n について n ≦ n^2 ≦ n^3」を使う．
一般に，2以上のどんな整数 k についても，「Ｏ(n^2) の関数は常に Ｏ(n^k) である」
を証明できる．Ｏ記法は，上から押さえるのに使える(関数値の増え方が同じかより速い)
関数の例を一つ示すだけで，下限を示すものではないことに注意する．

(3) 背理法で証明する以外に，Ｏ記法の定義の否定に沿って証明する方法もある．
証明が理解できない場合は，資料集の類似の証明中の解説も読むとよい．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/