5

私はCLRS第3版を独学で学んでいます。これは、すべての人へのサービスとしての回答とともに、私が遭遇した難しい質問の1つです。

7.4-5 入力が「ほぼ」ソートされている場合の挿入ソートの高速実行時間を利用することで、実際のクイックソートの実行時間を改善できます。k要素が少ないサブアレイでクイックソートを呼び出すときは、サブアレイをソートせずに単純に戻るようにします。クイックソートのトップレベルの呼び出しが戻った後、配列全体で挿入ソートを実行して、ソートプロセスを終了します。O(nk+nlg(n/k))この並べ替えアルゴリズムは予想される時間内に実行されると主張します。k理論的にも実際的にも、どのように選ぶべきでしょうか？

4

3 に答える 3

3

方程式を評価するnlgn > nk + nlog(n/k)と、が得られlog k > kます。それは不可能です。したがって、理論的には不可能です。しかし実際には、挿入ソートとクイックソートには一定の要因が関係しています。このpdfで説明されている解決策を見てください。あなたはあなたの答えを更新したいかもしれません。。

于 2012-09-08T13:21:19.520 に答える
2

実際、答えはk = 8です。

取得するアルゴリズムは、2つの無名関数の合成です。1つはで、もう1つO(nk)はですO(n lg n/k)。これらの無名関数は、平均的な大文字小文字の定数を隠します。挿入ソートn^2/4は平均的なケースで時間内に実行され、ランダム化されたクイックソートは1.386 n lg n平均的なケースで実行されます。の値がに等しいk値を最小化する値を見つけたいと思います。これは、関数の最大値を見つけることを意味します。その最大値はで発生します。nk/4 + 1.386( n lg n/k )nk/4 + 1.386 n lg n - 1.386 n lg k1.386 lg k - k/4k = 8

于 2013-04-25T10:08:57.287 に答える
0

1葉のサイズは〜の間で等しい確率がありますk。
したがって、葉の予想サイズはですk/2。
予想される葉のサイズがその場合、そのような葉が予想されk/2ますn/(k/2)=(2n)/k。
簡単にするためにn/k、そのような葉を期待し、各葉の期待サイズはであるとしましょうk。
の予想実行時間はINSERTION-SORTですO(n^2)。
演習5.2-5と問題2-4cでそれがわかりました。
したがって、予想されるINSERTION-SORT使用時間はですO((n/k)*(k^2))=O(nk)。
パーティショングループのサイズが大きいkと予想される場合、再帰ツリーの高さは、より早くlgn-lgk=lg(n/k)停止すると予想されるため、予想されます。 があるlgk
O(n)再帰ツリーの各レベルでの操作。
それは私たちをに導きO(nlg(n/k))ます。
予想される実行時間はであると結論付けO(nk+nlg(n/k))ます。

理論的には、を選択する必要があります。k=lgnこれにより、予想される最良の実行時間が得られるからですO(nlgn)。

実際には、実行するよりもパフォーマンスが向上kする値の1つを選択する必要があります。lgnRANDOMIZED-QUICKSORT

答えの2番目の部分では、big-O表記がかなり緩く使用されているため、より正確な選択kについては、Ankushによる2番目の答えに示されているリンクをたどってください。

于 2012-03-05T17:22:06.657 に答える