0

最近、Introduction To Algorithms Edition 3からこの問題に出くわしました

問題 2-1:

マージ ソートはO(n logn)最悪の場合に実行され、挿入ソートは で実行されますが、O(n^2)問題のサイズが小さい場合は後者の方が高速に実行されます。長さkのn/kサブリストが挿入ソートを使用してソートされ、標準のマージ メカニズムを使用してマージされる、マージ ソートの変更を検討してください。

(A) 挿入ソートが、それぞれの長さが k の n/k サブリストをO(nk)最悪の場合の時間でソートできることを示します。

与えられた答えは次のとおりです。

回答:挿入ソートは、最悪の場合、k 要素リストごとに (k^2) 時間かかります。したがって、k 要素の n/k リストの並べ替えには、それぞれ (k^2 n​​/k) = (nk) の最悪の場合の時間がかかります

与えられたデータから (k^2 n​​/k) を取得するにはどうすればよいですか?? 私はこれをまったく理解していません。説明をいただければ幸いです。

4

1 に答える 1

3

サブリストの長さは k であるためk^2、各サブリストに対して挿入ソートが必要です。現在、n/k合計でサブリストがあるため、n/k*k^2はnk. ここでの重要な理解は、n/k多数のサブリストがあり、挿入ソートはk^2それぞれをソートするのに時間がかかるということです。

注意すべきもう1つのことは、マージソートが持っていることを知っていることO(n logn)は、実際にはこの問題にとってまったく重要ではないということです。なぜなら、リスト全体をソートする時間は要求せず、すべてのサブリストをソートする時間だけを要求するからです。

于 2013-08-23T17:52:50.667 に答える