問題
マージソートの空間計算量に関する記述として最も適切なものはどれか。
選択肢
- 1配列実装では追加領域 O(n) が必要で、インプレースではない
- 2ヒープソートと同様にインプレースで O(1) の追加領域で済む
- 3再帰スタックを除けば O(log n) で済む
- 4常に O(n^2) の追加領域が必要
正解
1. 配列実装では追加領域 O(n) が必要で、インプレースではない
詳しい解説を見る解説を閉じる
解説
配列でのマージソートは併合（merge）処理時に左右半分を一時バッファへコピーする必要があるため、O(n) の追加領域が必要で「インプレースではない」。一方、連結リストのマージソートはポインタ付け替えで O(1) 追加領域で実装でき、安定ソートで Java の Collections.sort などに採用される。ヒープソートは O(1) 追加領域でインプレースだが安定ではない。マージソートは最悪 O(n log n) を保証する点で大規模データに有効。
一問一答
全400問を繰り返し学習