選択ソートの計算量

選択問題 アルゴリズムとプログラミング
要素数 n の選択ソートの計算量(オーダ)はどれか。

解説を見る
選択ソートは、未整列部分から最小値を探して先頭と交換する操作を繰り返す。最小値探索が二重ループになるため計算量は O(n^2)。
誤答の解説
BO(n) では全要素の比較整列はできない。
CO(log n) は2分探索など。
DO(n log n) はマージソートなど効率的な整列。
ヒント

・毎回最小値を全体から探す二重ループ。

関連する問題

アルゴリズムとプログラミング バブルソートの最悪計算量 アルゴリズムとプログラミング 2分探索の計算量 アルゴリズムとプログラミング スタックの動作 LIFO アルゴリズムとプログラミング キューの特徴 FIFO アルゴリズムとプログラミング 5の階乗の値

← 基本情報の一覧へ