平成14年秋期試験午前問題 問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)

Pagetop