![]()
平成15年 秋期 基本情報技術者 午後 問03
問03 プログラムの実行時間プログラムの実行時間に関する次の記述を読んで,設問に答えよ。 処理するデータ量によって,プログラムの実行時間がどのように変化するかを考えるときに, オーダ(という概念)を用いる。 例えば, n 個のデータを処理する最大実行時間が C n 2 ( C は定数)で抑えられるとき, 実行時間のオーダが n 2 であるという。
表 オーダの例
設問 次の記述中の
プログラムの各行の実行時間が一定であり,その時間を k と考える
(行番号 5,12,14 についても k だけの時間を要す)。
このとき,α部分の実行時間は 規則 1:順次処理で構成されている部分は,実行時間の最も長い行のオーダが, 全体の実行時間のオーダとなる。 規則 2:繰返し処理で構成されている部分は,繰り返される部分のオーダに繰返し数を
掛けた値のオーダ(定数は無視する)が,全体の実行時間のオーダになる。
行番号 10 と 11 の実行時間のオーダは,規則1から1となる。
行番号 9 〜 12 は行番号 10 と 11 を n 回繰り返すので,
ここのオーダは規則2から
したがって,プログラム全体の実行時間のオーダは
〔プログラム〕 (行番号)
a に関する解答群 ア 2 kn + k イ 2 kn +2 k ウ 3 kn + k エ 3 kn +2 k オ 4 kn + k カ 4 kn +2 k
b 〜 e に関する解答群 ア log2 n イ n ウ n log2 n エ n 2 オ n 3
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
©2004-2024 情報処理試験.jp
|
プライバシーポリシー・著作権・リンク
|
お問合わせ
| ||||||||