私は自己学習の第3版であり、ここではと遭遇した厄介な質問の1つであり、答えはです。クイックソートと挿入ソートハイブリッドの予想実行時間
7.4から5 私たちは、その入力が「ほぼ」ソートされる挿入ソートの 速い実行時間を活用して、実際にはクイックソートの実行されている時間を向上させることができます。 k個未満の要素を持つ部分配列に対して クイックソートを呼び出すと、 部分配列をソートせずにそのまま返します。クイックソートへのトップレベルの呼び出しが返された後、ソートプロセスを完了するために配列全体に挿入の並べ替え を実行します。この並べ替えアルゴリズム が予想時間でO(nk+nlg(n/k))で実行されると主張します。理論的には の両方で、実際にはkを選択する必要がありますか？
評価式nlgn > nk + nlog(n/k)の場合、log k > kが得られます。それは不可能です。したがって理論的には不可能です。しかし、実際には、挿入ソートやクイックソートには一定の要素があります。このpdfで解説されている解決策を見てください。あなたはあなたの答えを更新したいかもしれません。 。
葉のサイズは、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の場合は、lgkを先に停止する予定であるため、再帰ツリーの高さはlgn-lgk=lg(n/k)になると予想されます。
再帰ツリーの各レベルには、O(n)操作があります。
これはO(nlg(n/k))につながります。
予想される実行時間はO(nk+nlg(n/k))であると結論づけます。
理論的には、O(nlgn)という最高の実行時間が得られるので、理論的にはk=lgnを選ぶ必要があります。
実際には、RANDOMIZED-QUICKSORTを実行するよりもパフォーマンスが向上するlgnの値のいずれかにkを指定する必要があります。
答えの2番目の部分はbig-O表記法をかなり緩やかに使用しています。したがって、より正確な選択はkです。Ankushの2番目の答えに示されているリンクに従ってください。
あなたの答えは多少間違っています。あなたが理論的に言うことができる最高のところは、kはk = O（lg n）のような関数でなければならないということです。 kを正確に選択するには、挿入ソートとクイックソートに含まれる平均の大文字小文字定数を調べる必要があります。 –
フィードバックをいただきありがとうございます。最初に質問とその答えを投稿したとき、私は質問の最初の部分にもっと興味を持ち、ある意味では2番目の部分をスキップしました。 –
あなたもOpenUで勉強していますか？私たちはこの学期にママンにこの質問をしました。 –
実際、答えはk = 8です。
あなたが得るアルゴリズムは、2つの匿名関数の構成です。そのうちの1つはO(nk)であり、もう1つは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 kになります。これは、関数1.386 lg k - k/4の最大値を見つけることを意味します。その最大値はk = 8です。
優れた観測、ありがとう。私は答えを編集します。 –