【基本情報技術者試験平成14年秋期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成14年秋期基本情報技術者午前問13

問13　　 整列の比較回数のオーダ

　未整列の配列 A [ i ]（ i ＝1，2，...， n ）を，次のアルゴリズムで整列する。要素同士の比較回数のオーダを表す式はどれか。

〔アルゴリズム〕

(1)　 A [ 1 ] ～ A [ n ] の中から最小の要素を探し，それを A [ 1 ] と交換する。

(2)　 A [ 2 ] ～ A [ n ] の中から最小の要素を探し，それを A [ 2 ] と交換する。

(3)　同様に，範囲を狭めながら処理を繰り返す。

ア　 O (log₂ n )　　　　イ　 O ( n )　　　　ウ　 O ( n log₂ n )　　　　エ　 O ( n ²)

解説

　問題のアルゴリズムは、選択法であり、比較回数は、 O (n ²)　である。