以下の関数の計算量のオーダーをそれぞれ示す問題です。 (a) $f(n) = \sqrt{n} + \log_2 2^n$ (b) $f(n) = 1000 \cdot 2^n + 0.01n^n$ (c) $f(n) = n \log_2 n + n \sqrt[3]{n}$ (d) $f(n) = n^2 \log_2 n^2 + n^{2.01}$

## 設問2：計算量のオーダー

1. 問題の内容

以下の関数の計算量のオーダーをそれぞれ示す問題です。

(a) $f(n) = \sqrt{n} + \log_2 2^n$

(b) $f(n) = 1000 \cdot 2^n + 0.01n^n$

(c) $f(n) = n \log_2 n + n \sqrt[3]{n}$

(d) $f(n) = n^2 \log_2 n^2 + n^{2.01}$

2. 解き方の手順

各関数について、漸近的な振る舞い（$n$ が非常に大きくなったときの振る舞い）を考え、支配的な項を見つけます。

(a) $f(n) = \sqrt{n} + \log_2 2^n = \sqrt{n} + n \log_2 2 = \sqrt{n} + n$

$n$ が大きくなるにつれて、$n$ の方が $\sqrt{n}$ よりも大きくなるため、$f(n)$ のオーダーは $O(n)$ です。

(b) $f(n) = 1000 \cdot 2^n + 0.01n^n$

$n$ が大きくなるにつれて、$n^n$ は $2^n$ よりも急速に大きくなるため、$f(n)$ のオーダーは $O(n^n)$ です。

(c) $f(n) = n \log_2 n + n \sqrt[3]{n} = n \log_2 n + n \cdot n^{1/3} = n \log_2 n + n^{4/3}$

$n$ が大きくなるにつれて、$n^{4/3}$ は $n \log_2 n$ よりも大きくなるため、$f(n)$ のオーダーは $O(n^{4/3})$ です。

(d) $f(n) = n^2 \log_2 n^2 + n^{2.01} = n^2 (2 \log_2 n) + n^{2.01} = 2n^2 \log_2 n + n^{2.01}$

$n$ が大きくなるにつれて、$n^{2.01}$ は $n^2 \log_2 n$ よりも大きくなるため、$f(n)$ のオーダーは $O(n^{2.01})$ です。

3. 最終的な答え

(a) $O(n)$

(b) $O(n^n)$

(c) $O(n^{4/3})$

(d) $O(n^{2.01})$