クイックソートの最悪時間計算量として正しいものはどれか。ここで $n$ は整列する要素数とする。

正解：ウ　$O(n^2)$

解説

正解は「$O(n^2)$」です。クイックソートはピボットを基準に配列を2分割し、再帰的に整列します。ピボットが常に最大値または最小値になる場合（整列済みの配列で先頭要素をピボットにするなど）、分割が $n-1$ 個と0個に偏り、比較回数は $(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$ となるため $O(n^2)$ です。「$O(n\log n)$」は平均計算量であり、最悪ケースではありません（最悪でも $O(n\log n)$ を保証するのはマージソートやヒープソートです）。「$O(n)$」は比較ソートの下界 $\Omega (n\log n)$ を下回るため実現できません。「$O(2^n)$」は全探索などの指数時間アルゴリズムの計算量です。

• #計算量
• #ソート