アルゴリズムとプログラミング
平成23年度 秋期 基本情報技術者試験 午前 問3
コンピュータで連立一次方程式の解を求めるのに，式に含まれる未知数の個数の 3 乗に比例する計算時間が掛かるとする。あるコンピュータで 100 元連立一次方程式の解を求めるのに 2 秒掛かったとすると，その 4 倍の演算速度をもつコンピュータで 1,000 元連立一次方程式の解を求めるときの計算時間は何秒か。
- ア 5
- イ 50
- ウ 500
- エ 5,000
出典：平成23年度 秋期 基本情報技術者試験 午前 問3
答えと解説を見る
正解：ウ
覚える知識
計算量のオーダ(n³に比例する計算時間)の比例計算
計算時間がn³に比例するなら、nがk倍になると時間はk³倍になる。
この問題で必要なこと
計算時間はn³に比例するので10倍の元数で1000倍、演算速度4倍で1/4となり、2×1000/4=500秒。
ひっかけ
3乗でなく比例(10倍)や2乗(100倍)で計算した値、速度比を掛けた値が混ざる。
この知識の出題：本試験系 1 回・免除試験 8 回（公開問題での観測値）