5

さて、マージソートのシータ（NlogN）の最悪の場合の時間は知っていますが、そのオーバーヘッドは高く、マージが行われる再帰ツリーの最下部近くに現れます。サイズがKに達したら再帰を停止し、その時点で挿入ソートに切り替えることを提案した人がいます。この修正された漸化式の実行時間がtheta（NK + Nlog（N / k））であることを証明する必要がありますか？私はこの問題にどのように取り組むかについて空白にしています。

4

1 に答える 1

3

おそらく、この問題の漸化式を調べることから始めるのがよいでしょう。典型的なマージソートの場合、次のようになります。

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/KKK^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)

証明スケッチを提供するためにアルゴリズムを採用してから時間がかかりすぎましたが、それでニューロンが発火するはずです。

于 2011-01-31T08:24:06.267 に答える