sorting - マージソートの実行時間 :: すべての要素が同一

Question

すべての要素が同一のサイズ n の配列があるとします。O(n)はどうなる？線形になりますか？

Answer 1

これは、アルゴリズムの実装方法によって異なります。

マージソートの標準的な「バニラ」実装では、各ステップで必要なマージにはそれぞれ線形時間がかかるため、配列のソートに必要な時間は常に Θ(n log n) になります。

ただし、適切な最適化を行うことで、これを時間 O(n) で実行することができます。多くのマージソートの実装では、入力配列は継続的に変更されるため、ますます大きな範囲がソートされ、マージ ステップが発生すると、アルゴリズムは外部バッファを使用して 2 つの隣接するソートされた範囲をマージします。その場合、実行できる気の利いた最適化があります。マージを行う前に、最初の範囲の最後の要素が 2 番目の範囲の最初の要素以下であるかどうかを確認します。その場合、一緒に取得された 2 つの範囲は既にソートされているため、マージを行う必要はありません。

この最適化を実行し、すべての要素が既にソートされている配列をソートしようとするとします。何が起こるのですか？さて、mergesort を呼び出すたびに、さらに 2 つの再帰呼び出しが発生します。それらが返された後、並べ替えられた範囲のエンドポイントをチェックでき、それらが既に並べ替えられた順序になっていることに気付くため、これ以上行う作業はありません。全体として、これは呼び出しごとに O(1) の作業を行うため、アルゴリズムの時間の複雑さについて次の再帰関係があります。

T(n) = 2T(n/2) + O(1)

これは O(n) に解決されるため、線形作業のみが行われます。