平成14年秋期試験問題 午前問13
問13解説へ
未整列の配列A[i](i＝1，2，...，n)を，次のアルゴリズムで整列する。要素同士の比較回数のオーダーを表す式はどれか。
〔アルゴリズム〕
〔アルゴリズム〕
- A[1]～A[n]の中から最小の要素を探し，それをA[1]と交換する。
- A[2]～A[n] の中から最小の要素を探し，それをA[2]と交換する。
- 同様に，範囲を狭めながら処理を繰り返す。
- O(log2n)
- O(n)
- O(nlog2n)
- O(n2)
広告
解説
オーダー記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダー記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較ができます。
情報処理技術者試験に出題される整列アルゴリズムのオーダーは、
問われている整列方法は、「基本選択法」です。
したがって、正解は「エ」です。
情報処理技術者試験に出題される整列アルゴリズムのオーダーは、
- バブルソート、基本選択法、基本挿入法→O(n2)
- クイックソート、マージソート、ヒープソート→O(nlog2n)
問われている整列方法は、「基本選択法」です。
したがって、正解は「エ」です。
- 基本選択法
- 最大値を持つデータを探して、最後のデータと交換を行う整列法。n個のデータの計算量(オーダー)は、O(n2)
広告