整列アルゴリズムの計算量比較とは？せいれつあるごりずむのけいさんりょうひかく
整列アルゴリズムの計算量比較とは、整列法の選定に使う、平均と最悪の計算量の一覧。バブル・選択・挿入はどちらもO(n²)、マージとヒープはどちらもO(n log n)、クイックは平均O(n log n)に対し最悪だけがO(n²)へ落ちる。資源に制約のある実装では、平均値より最悪値と追加メモリ量のほうが決め手になる。
最終更新：2026-10-06
エンベデッドSPを最短で暗記・合格する →背景
同じ結果を得るのに、手順の違いだけで処理時間が桁で変わる。ただし資源が潤沢な環境と組込みとでは選定基準が違い、後者では平均が速いことより最悪実行時間が確定していることに価値がある。制御周期の中で回すなら、最悪でも間に合うと言えなければ採用できない。あわせて、スタックと作業領域の消費が実装メモリに収まるかも同時に判断する。
具体例
要素数が千から一万へ十倍になると、O(n²)の手法は所要時間がおよそ百倍、O(n log n)の手法は十数倍で済む。一方、要素数が数十に収まるセンサ値の中央値フィルタでは、定数倍が小さく追加メモリもスタックも要らない挿入ソートのほうが実測で速い。
試験での引っ掛け
クイックソートは平均こそ最速級だが、整列済みのデータで基準値の選び方が悪いと最悪O(n²)になる。組込みではこれに加えて、再帰の深さが読めないとスタックあふれの危険が乗る。マージソートは最悪もO(n log n)だが要素数ぶんの作業領域が要る。オーダだけで選ぶと、メモリとスタックの制約で実装できない。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。