平成14年秋期試験問題 午前問13

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
未整列の配列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