最適化されたmergesortの実行時間を証明するのは、シータ（nk + nlog（n/k））ですか？

Question

さて、Mergesortには最悪のケースのTheta（Nlogn）がありますが、そのオーバーヘッドは高く、合併が作られている再帰ツリーの底の近くに現れます。誰かが、サイズがKに達し、その時点で挿入並べ替えに切り替えると、再帰を停止することを提案しました。この修正された再発関係の実行時間がシータ（nk + nlog（n/k））であることを証明する必要がありますか？私はこの問題にアプローチする方法について鈍いです。

Answer 1

たぶん、この問題の再発関係を見ることが良いスタートです。典型的なmergesortについては、次のようになります。

T(N) = 2 * T(N / 2) + N

つまり、問題を半分のサイズの2つのサブ問題に分割し、N作業（マージ）を実行します。一定の時間がかかる基本ケースがあります。

これを私たちが持っている木としてモデル化します：

T(N)   =   N   ->   T(N / 2)   
               ->   T(N / 2)

       =   N   ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)
               ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)

これにより、の拡張が得られます

T(N) = N + 2N/2 + 4N/4 + ...
     = N + N + N ...

だから本当に私たちはそれがどれほど深くなるかを見る必要があります。私たちはそれを知っています iTHレベルはサブ問題で動作します N / 2^i サイズ。だから私たちの葉のノード（T(1)）レベルで発生します L どこ N / 2^L = 1:

N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L

だから私たちのランタイムはそうです N log N.

次に、挿入ソートを紹介します。私たちの木はこのようなものになります

T(N) = ... -> I(K)
           -> I(K)
             ...x N/K

言い換えれば、私たちはある程度のレベルになります L 解決する必要があります N/K サイズの挿入の問題 K. 。挿入ソートには、最悪のランタイムがあります K^2. 。だから葉にはこれほど多くの作業があります 合計で:

(N / K) * I(K)
= (N / K) * K * K
= N * K

しかし、私たちはまた、その犠牲を払って、やるべきこともたくさんあります N 前に説明したように、ツリーのレベルごと。以前の方法に戻ると、見つけましょう L （サイズのサブ問題に達する前のレベル数 K したがって、挿入に切り替えます）：

N / 2^L = K
N / K = 2^L
L = log (N/K)

だから合計で私たちは持っています

O(N) = N * K + N * log (N/K)

アルゴリズムを採用して証明スケッチを提供してから長すぎましたが、それはあなたのニューロンを発射するはずです。