(a) O-記法に関する穴埋め問題と、(b) 3つのアルゴリズム A, B, C の計算量 $f_A(n) = \sqrt{n} \log_2 n$, $f_B(n) = n \log_2 \sqrt{n}$, $f_C(n) = n \log_{10} n$ が与えられたとき、ある程度大きな $n$ に対して、最も効率が良いアルゴリズム、最も効率が悪いアルゴリズム、計算量のオーダーが等しいアルゴリズムをそれぞれ選択肢から選ぶ問題。

1. 問題の内容

(a) O-記法に関する穴埋め問題と、(b) 3つのアルゴリズム A, B, C の計算量 $f_A(n) = \sqrt{n} \log_2 n$, $f_B(n) = n \log_2 \sqrt{n}$, $f_C(n) = n \log_{10} n$ が与えられたとき、ある程度大きな $n$ に対して、最も効率が良いアルゴリズム、最も効率が悪いアルゴリズム、計算量のオーダーが等しいアルゴリズムをそれぞれ選択肢から選ぶ問題。

2. 解き方の手順

(a)

* O-記法はアルゴリズムの計算量を表す記法であり、入力サイズ $n$ が十分に大きいときの漸近的な振る舞いを記述する。

* O-記法は、計算量の上界を表す。

(b)

* $f_A(n) = \sqrt{n} \log_2 n$

* $f_B(n) = n \log_2 \sqrt{n} = n \cdot \frac{1}{2} \log_2 n = \frac{1}{2} n \log_2 n$

* $f_C(n) = n \log_{10} n = n \cdot \frac{\log_2 n}{\log_2 10} = \frac{1}{\log_2 10} n \log_2 n$

ここで、$n$ が十分に大きいとき、$\sqrt{n}$ は $n$ より小さいので、$f_A(n)$ は $f_B(n)$ や $f_C(n)$ より小さくなる。また、$f_B(n)$ と $f_C(n)$ は $n \log_2 n$ に定数をかけた形なので、オーダーは同じである。$\log_2 10 \approx 3.32$ であるから$\frac{1}{2} < \frac{1}{\log_2 10}$なので、$f_B(n) < f_C(n)$。

したがって、ある程度大きな $n$ に対して、

* 最も効率が良い（計算量が小さい）アルゴリズムは A。

* 最も効率が悪い（計算量が大きい）アルゴリズムは C。

* 計算量のオーダーが等しいアルゴリズムは B と C。

3. 最終的な答え

(1): (イ)

(2): (ア)

(3): (ア)

(4): (ウ)

(5): (ウ)