插入排序在歸併小的子陣列

Question

我同時解決「言由Cormen算法」出了問題，問題如下卡住，

插入排序在合併小數組排序

雖然合併排序在O（n logn）最差情況下運行，並且插入排序在O（n^2）中運行，後者對於小問題運行速度更快。考慮修改合併排序，其中使用插入排序對長度爲k的子列表進行排序，然後使用標準合併機制進行合併。

至K長度的這些N/K的子列表排序花費O（NK）和合並它需要O

所以修改算法將這些N/K的子列表（N LG（N/K）） O（nk）+ O（n lg（n/k）），

作爲n的函數，k的最大漸近（Θnotation）值是多少，其中修改後的算法具有與標準合併相同的漸近運行時間分類？

在實踐中應該如何選擇k？

這是兩個事情讓我堅持，任何形式的幫助表示讚賞，感謝提前:)

Answer 1

的第一個問題是問，基本上可以k爲大於或等於給LG n和仍具有Θ（n lg n）的漸近階。如果它大於，我們知道兩種排序算法的組合不如合併排序那樣有效。所以我們假設k =Θ（lg n）。如果插入lg n，其中k在您的遞歸關係中，使得T（nlgn + n lg（n/lg（n））並解決您在Θnotation中將具有最大漸近值的問題。如果我們爲nk和nlgn添加一些正整數，我們知道k取決於這兩個正整數之間的比率，希望這有助於！

前XNK + ynlgn

x和y是正的常數

所以K = X/Y，因爲最大限度地減少了AB表達。所以k不依賴於n。

Answer 2

對不起，我想我可以添加一些關於第二個問題的額外信息。 據羅伯特·塞奇威克和凱文·韋恩

寫的算法（第4版）一書切換到插入排序爲小型子陣列（長度小於或等於15，說吧）將通過提高運行>典型的歸併執行時間10至15％。