基本情報技術者 2011年 秋期 午前（科目A） 問03

コンピュータで連立一次方程式の計算時間が未知数の3乗に比例する場合の問題【午前2 解説】

要点まとめ

• 結論：未知数の個数$n$の3乗に比例するという条件から計算すると、4倍速の機で1000元連立一次方程式を解く時間は500秒になります。
• 根拠：基準は100元で2秒、規模比は$(1000/100{)}^3=10^3$、速度が4倍なら時間は$2\times 1000/4=500$秒となります。
• 差がつくポイント：比の扱い（立方比）と計算機速度の逆比例を混同しないこと、桁（10^3）を正確に扱うことが重要です。

正解の理由

よくある誤解

• 比が「線形（n倍）」だと誤解してしまい、$1000/100=10$を使って計算してしまうミス。実際は立方比です。
• 演算速度の影響を掛け算すべきところで割ってしまうなど、速度と時間の逆比例関係を逆に扱う誤り。
• 途中の桁（10^3）や単位の取り扱いを誤り、桁落ちや桁上げを間違えること。

解法ステップ

1. 比較したい未知数の比を求める：$\frac{1000}{100}=10$。
2. 計算時間が3乗に比例するので規模比の立方を取る：$10^3=1000$。
3. 基準時間に掛ける：$2\text{秒}\times 1000=2000\text{秒}$（同じ演算速度の場合）。
4. 新しいマシンは4倍速なので時間は演算速度に逆比例：$\frac{2000}{4}=500\text{秒}$。
5. よって答えは500秒（選択肢ウ）。

選択肢別の誤答解説

• ア: 5 — あまりに小さく、規模増加の影響（立方）が無視されている。線形や一桁のミスが原因。
• イ: 50 — 規模比を$10^2$や$10$で誤処理した可能性がある。例えば$2\times 25=50$のような計算誤り（速度や立方を取り違え）。
• ウ: 500 — 正解。上記の通り $(1000/100{)}^3$ と速度4倍の逆比例を正しく適用した結果です。
• エ: 5,000 — 演算速度を無視して単純に規模比の立方だけを掛けた場合の値（$2\times 1000=2000$でもないが、5000はさらに別の桁誤り）。おそらく桁を一つ多く見積もったミス。

補足コラム

• この問題はアルゴリズム解析でよく出る「計算量」の考え方を応用しています。連立一次方程式の一般的な直接解法（ガウス消去法など）は計算量が$O(n^3)$で近似されるため、未知数が増えると急速に計算時間が増加します。
• 実運用ではアルゴリズムの違いや行列の疎密、並列化により実効時間は変わりますが、試験問題では「比例関係」を素直に使うのが正解です。
• 単位確認（秒や分）や桁（10のべき）の扱いに注意してください。

FAQ