HOME»基本情報技術者試験掲示板»情報処理分野の問題について
投稿する

[2949] 情報処理分野の問題について

 クマさん(No.1) 
今解いている問題が解説を見ても判りません。

問  あるコンピュータシステムにおいて、1,000,000個のデータをバブルソートを用いて整列するために必要な時間は100,000秒であった。このコンピュータシステムにおいて、10,000個のデータをバブルソートを用いて整列するために必要な時間は約何秒であると推定できるか。ここで、バブルソートを用いて整列するために必要な時間は、データ同士の比較回数に比例するものとする。

解説
@バブルソートにおけるn個のデータの比較回数=n×(n-1)/2≒n^2/2
Akを定数とすると、1,000,000のデータのバブルソートにおいて、次の式が成立する。
    k×(1,000,000)^2/2=100,000(秒)
Bk=2×1,000,000/(1,000,000)^2
    =2/1,000,000
C10,000のデータのバブルソートに必要な時間=k×(10,000)^2
    =(2/10,000,000)×(10,000)^/2
    =10(秒)

このkが一体何を求めているのかさっぱりです。

ちなみに自分なりに@を使って計算しましたが?

(100,000,000)^2/2=500,000,000,000
(100,000)^2/2=50,000,000
500,000,000,000/50,000,000
=10000
よって、1,000,000個のデータを整列する時間は10,000個のデータを整列する時間の10000倍  と考えたのですが……何が間違っているのでしょうか
2021.02.26 18:16
いいね正解大卒さん(No.2) 
FE ブロンズマイスター
kは「1回の比較当たり何秒かかるか」です。
k×(1,000,000)^2/2=100,000(秒)
(比較1回当たり秒)*(比較回数)=(比較に要する時間の合計)
になるでしょう?

>>(100,000,000)^2/2=500,000,000,000
>>(100,000)^2/2=50,000,000
2つ目の式、100,000という数字がどこから出てきたのかが謎ですが……(nの単位は個なので単位が秒の数字を代入しても意味がない)
正しくはこうです

100,000,000個のデータの比較回数Aは
A = 100,000,000^2/2 = 10^12/2
10,000個のデータの比較回数Bは
B = 10,000^2/2 = 10^8/2
A / B
=(10^12/2) / (10^8/2)
= 10^4
よってAはBの10^4倍となり、題意より、100,000,000個のデータは10,000のデータに比べ整列に必要な時間も10^4倍となる。
100,000 / 10^4 = 10
以上より求める時間は10秒
2021.02.26 23:48

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop