HOME»基本情報技術者試験掲示板»H19 春 午後問４
投稿する
H19 春 午後問４ [1447]
あああさん(No.1)
H19 春 午後問４の、設問３のやり方がイマイチよくわかりません・・・
外のサイトにも解説が無いようなので、教えてほしいです。
外のサイトにも解説が無いようなので、教えてほしいです。
2018.10.05 11:33
助け人さん(No.2)
★FE ゴールドマイスター
この頃の問題はとても難しく、最近ではまず出ないでしょうが、チャレンジし甲斐があります。
1,000個のデータの整列時間は、InsertSortが10に対して、QuickSortが1です。1,000,000個のデータの整列時間が、1,000個の場合に比べて何倍になるかを求めます。
InsertSort
n^2に比例するため、1,000,000^2／1,000^2倍です。
これを計算すると、10^12／10^6＝10^6倍となり、1,000個の場合の時間が10ですから、10^7です。
QuickSort
n log2 nに比例するため、1,000,000×log2 1,000,000／(1,000×log2 1,000)倍です。
これを計算すると、10^6×20／(10^3×10)＝2×10^3倍となり、1,000個の場合の時間が1ですから、2×10^3です。
QuickSortの時間／InsertSortの時間＝2×10^3／10^7＝2／10^4＝1／5,000
よって、正解は5,000(ウ)
1,000個のデータの整列時間は、InsertSortが10に対して、QuickSortが1です。1,000,000個のデータの整列時間が、1,000個の場合に比べて何倍になるかを求めます。
InsertSort
n^2に比例するため、1,000,000^2／1,000^2倍です。
これを計算すると、10^12／10^6＝10^6倍となり、1,000個の場合の時間が10ですから、10^7です。
QuickSort
n log2 nに比例するため、1,000,000×log2 1,000,000／(1,000×log2 1,000)倍です。
これを計算すると、10^6×20／(10^3×10)＝2×10^3倍となり、1,000個の場合の時間が1ですから、2×10^3です。
QuickSortの時間／InsertSortの時間＝2×10^3／10^7＝2／10^4＝1／5,000
よって、正解は5,000(ウ)
2018.10.05 16:41