基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成15年 秋期 基本情報技術者 午後 問03
問03   プログラムの実行時間

 プログラムの実行時間に関する次の記述を読んで,設問に答えよ。

処理するデータ量によって,プログラムの実行時間がどのように変化するかを考えるときに, オーダ(という概念)を用いる。 例えば, n 個のデータを処理する最大実行時間が C n 2 C は定数)で抑えられるとき, 実行時間のオーダが n 2 であるという。

  表 オーダの例

実行時間 オーダ
C (定数) 1
100 n n
3 n 2 + 5 n + 1000 n 2

基本情報技術者試験


設問 次の記述中の に入れる適切な答えを, 解答群の中から選べ。 なお,解答は重複して選んでもよい。

 プログラムの各行の実行時間が一定であり,その時間を k と考える (行番号 5,12,14 についても k だけの時間を要す)。 このとき,α部分の実行時間は となるので, オーダは となる。 β部分もα部分と同様に計算し,両者の実行時間を足してからプログラム全体のオーダを 求めることができる。 しかし,次の二つの規則を用いることで,より簡単にオーダを求めることが可能となる。

規則 1:順次処理で構成されている部分は,実行時間の最も長い行のオーダが, 全体の実行時間のオーダとなる。

規則 2:繰返し処理で構成されている部分は,繰り返される部分のオーダに繰返し数を 掛けた値のオーダ(定数は無視する)が,全体の実行時間のオーダになる。
例えば,繰り返される部分のオーダが n 2 で, 繰返し数が 100 n ならば,繰返し処理全体のオーダは, n 3 である。

 行番号 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

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]