令和元年度(再試験) III-2

解説

この問題で問われていること

階乗オーダーの計算量が、入力サイズの増加により爆発的に増える様子を、数値で見積もる問題。

解き方

① 計算時間はn!に比例。1週間=7×24×3600≒60万秒
② 12!÷4!=5×6×…×12≒2×10⁷ → 約2,000万秒 → 2,000万÷60万≒33週
③ 約33週(①)

正解が正しい理由

計算時間は、n!に比例するとみなす。n=4のとき、4!=24を1秒で計算できるので、1秒あたり24単位の処理ができる。n=12のときは、12!=479,001,600単位で、必要な時間は、479,001,600÷24=19,958,400秒。これを日に換算すると、19,958,400÷86,400≈231日で、約33週に相当する。したがって①が最も適切である。

この問題で必要な基礎

■ n!(nの階乗)
n!は1からnまでの整数を全て掛けた数です。4!=1×2×3×4=24、12!=1×2×…×12=479,001,600です。

■ O(n!)の意味
計算時間がn!に比例する、という意味です。そのため、n=12の計算時間は、n=4のときの12!÷4!倍になります。問題のサイズが3倍になっても、計算時間は3倍ではなく、約2,000万倍に増えます。

各選択肢について

• ① 約19,958,400秒≈231日≈33週で、見積りと一致する。これが正答。
• ② 24日は、この見積りより1桁小さい。
• ③ 12時間は、この見積りよりはるかに短い。
• ④ 6秒は、3倍(n=12はn=4の3倍)として、計算量を単純に線形に見積もった値などで、n!の増え方を考慮していない。
• ⑤ 3秒は、問題サイズに比例(線形)するという誤った見積りに近い値(1秒×3倍)。

覚えるべきポイント

n!はnの増加とともに爆発的に増加する。n=4→12で、12!/4!≈2×10^7倍。組合せ爆発を起こす問題は、大きなnでは現実的な時間で解けなくなる。