アルゴリズムとプログラミング
基本情報技術者試験｜クイックソートの平均計算量と、最悪計算量の
クイックソートの平均計算量と、最悪計算量の組合せとして正しいものはどれか。
ア平均O(n)で最悪はO(n log n)である
イ平均も最悪も常にO(n log n)である
ウ平均O(n log n)、最悪はO(n^2)
エ平均O(n^2)で最悪はO(n log n)である
正解
ウ．平均O(n log n)、最悪はO(n^2)
クイックソートは基準値で分割し再帰する。分割が均等に近い平均はO(n log n)だが、毎回片側に偏る最悪はO(n^2)となるため正しい。
?選択肢ごとの解説
ア ×平均O(n)は比較ソートの下限O(n log n)を下回り得ず、最悪O(n log n)も偏り時の劣化を見落とした誤りである。
イ ×平均も最悪もO(n log n)なのはマージソートやヒープソートであり、クイックソートは最悪でO(n^2)に劣化する。
ウ ○クイックソートは基準値で分割し再帰する。分割が均等に近い平均はO(n log n)だが、毎回片側に偏る最悪はO(n^2)となるため正しい。
エ ×平均O(n^2)は実態より悪く見積もった誤りで、最悪をO(n log n)とする点も偏り時の劣化を見落としている。
アルゴリズムとプログラミングの他の問題
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0032