オーダ表記（計算量）

オーダ表記 O の定義を使って，左の関数が右の関数の定数倍におさまるかを判断する問題です。

f(n)＝O(g(n)) は，n が大きくなれば f(n) がいつも g(n) の c 倍以下におさまるという意味です。

f(n) ÷ g(n) が限りなく大きくならなければ正，大きくなれば誤です。増え方は log n ＜ n のべき ＜ aⁿ ＜ 2 の 2ⁿ 乗の順です。

ア：(5n³＋1) ÷ n³ ＝ 5 ＋ 1/n³ で，6 以下です。c ＝ 6 で成り立ちます。正しいです。

イ：nlog₂n ÷ n^1.5 ＝ log₂n ÷ √n です。log はどんな小さなべきよりゆっくり増えるので，比は 0 に近づきます。正しいです。

ウ：n³3ⁿ ÷ 4ⁿ ＝ n³ × (3/4)ⁿ です。(3/4)ⁿ は指数的に小さくなり，n³ の増え方に勝つので，比は 0 に近づきます。正しいです。

エ：両方の log₂ をとると，左は 2ⁿ，右は n¹⁰⁰ × log₂10 です。指数の 2ⁿ はべきの n¹⁰⁰ にいずれ勝つので，左のほうが速く増え，定数倍ではおさまりません。誤りです。答えは ア 正，イ 正，ウ 正，エ 誤

• f(n)＝O(g(n))：n が大きいとき f(n) ≦ c・g(n)。「比が限りなく大きくならないか」で判断する
• 増え方の順：log n ＜ √n ＜ n ＜ n² ＜ … ＜ 2ⁿ ＜ 3ⁿ ＜ 2 の 2ⁿ 乗。指数はべきに勝ち，べきは log に勝つ
• 指数どうしは底で決まる。3ⁿ は 4ⁿ より小さく，n³ を掛けても追いつかない
• 指数の指数をくらべるときは，両方の log をとって中身をくらべる