ソフトウェア開発技術者平成16年春期 午前問8

問8

大きさ n の問題をT(n)秒で解くプログラムがある。このプログラムを用いて104秒以内で解ける最大の問題の大きさは,103秒以内で解ける最大の問題の大きさの約3.2倍になる。T(n)を表す式はどれか。
  • 100n
  • 5n2
  • n3/2
  • 2n

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

解説

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

 T(n)=103

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

 T(3.2n)=104

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

 104×103=10(倍)
 T(3.2n)÷T(n)≒10(倍)

これを利用して選択肢の各式のうち、条件を満たすものを見つけます。
  •  100×3.2n/100n
    =3.2×100n/100n
    =3.2(倍)
  •  5×(3.2n)2/5n2
    =5×3.22×n2/5n2
    =3.22×5n2/5n2
    =3.22
    =10.24≒10(倍)
    したがって T(n)=5n2 が適切です。
  •  ((3.2n)3/2)/(n3/2)
    =(32.768n3/2)/(n3/2)
    =(32.768n3×2)/(2×n3)
    =32.768n3/n3
    =32.768(倍)
  •  23.2n/2n
    =23.2n-n
    =2n(3.2-1)
    =22.2n(倍)
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop