探索とソートは AP科目Aで確実に1〜2問、科目B問3でも頻繁に題材になります。計算量と特徴をセットで覚えるのが鉄則。
砂原 ニコ
ソートこんなにいっぱいあって、あたし覚えられないよー!
緒方 ナオミ 先生
覚えるべきはこの5つよ: バブルソート・挿入ソート・選択ソート・クイックソート・マージソート。
あとはそれぞれの計算量と『安定/不安定』を押さえればいいの。
鳴海 理央
バブル・挿入・選択は O(n²)、クイックは平均 O(n log n) ・最悪 O(n²)、マージは常に O(n log n)。
AP科目Aは計算量を問う問題が多いです。
藤咲 まりあ
うぅ〜ん、『安定』ってなんですかぁ?
鳴海 理央
同じキーの順序が保たれるかどうか。
バブル・挿入・マージは安定、クイック・ヒープ・選択は不安定です。
砂原 ニコ
じゃあ探索のほうはどうなの?
緒方 ナオミ 先生
線形探索 は O(n)、二分探索 は O(log n) (整列済みが条件)、ハッシュ は平均 O(1)。
データ量が増えたときの差は劇的よ。
確認クイズ
クイックソートの平均時間計算量・最悪時間計算量の組合せとして正しいものはどれか。
- 平均 O(n log n) / 最悪 O(n log n)
- 平均 O(n log n) / 最悪 O(n²)
- 平均 O(n²) / 最悪 O(n²)
- 平均 O(n) / 最悪 O(n²)
こたえを見る
正解: 2. 平均 O(n log n) / 最悪 O(n²)
クイックソートは平均 O(n log n) ですが、ピボット選択が極端に偏ると O(n²) に劣化します。マージソートは常に O(n log n) で、最悪を避けたい場合に選ばれます。