応用情報技術者 試験情報＆徹底解説

nを10³秒以内で解ける最大の問題の大きさとするとき、問題量と解く時間の関係は以下の式で表せます。

　T(n)＝10³

さらに最大でnの3.2倍の大きさのプログラムを10⁴秒以内で解けるので、10⁴秒の場合の問題量と解く時間の関係も同じように表せます。

　T(3.2n)＝10⁴

この2つの式から、以下の関係を導けます。

　10⁴×10³＝10(倍)
　T(3.2n)÷T(n)≒10(倍)

これを利用して選択肢の各式のうち、条件を満たすものを見つけます。

• 　100×3.2n／100n
  ＝3.2×100n／100n
  ＝3.2(倍)
• 　5×(3.2n)2／5n²
  ＝5×3.2²×n²／5n²
  ＝3.2²×5n²／5n²
  ＝3.2²
  ＝10.24≒10(倍)
  したがって T(n)＝5n² が適切です。
• 　((3.2n)³／2)／(n³／2)
  ＝(32.768n³／2)／(n³／2)
  ＝(32.768n³×2)／(2×n³)
  ＝32.768n³／n³
  ＝32.768(倍)
• 　2^3.2n／2ⁿ
  ＝2^3.2n-n
  ＝2^n(3.2-1)
  ＝2^2.2n(倍)