快速排序分析

Question

問：

這裏的快速排序的修改：每當我們有一個子列表十個項目或更少，我們使用選擇排序，而不是進一步遞歸快速排序排序的子表。這是否會改變quicksort的大時間複雜度？說明。

在我看來，大哦時間的複雜性會改變。我們知道選擇排序是O（n^2），因此排序10個或更少的子列表將花費O（n^2）。在我們到達包含10個或更少項目的子列表之前，我們將使用快速排序並繼續對列表進行分區。所以最後我們會有O（nlogn + n^2），它是O（n^2）。

我正確嗎？如果不是，有人可以解釋爲什麼嗎？

Answer 1

時間複雜度實際上不受影響的原因是10是一個常數項。無論整個陣列有多大，總是需要一定的時間來對大小爲10或更小的子陣列進行排序。如果你用一百萬個元素對一個列表排序，那麼這個常量10在排序列表所需的實際時間中將扮演一個非常小的角色（大部分時間將用於遞歸地將原始數組分割成子陣列）。

如果對10個元素的列表進行排序需要一定的時間，則在每個遞歸步驟對數組進行分區是線性的，並且最終得到10個或更少的log n子數組，最終會得到O（n log n + log n），這與O（n log n）相同。

說選擇排序是O（n^2）意味着算法的運行時間隨着輸入的大小以二次方增加。對具有不變元素數組的數組進行選擇排序總是需要一定的時間，但如果您要比較不同大小的數組上的選擇排序的運行時間，則會看到運行時間的平方增加爲輸入大小線性變化。

Answer 2

大O的複雜性不會改變。請閱讀Master Method（aka Master Theorem）https://en.wikipedia.org/wiki/Master_theorem

如果您認爲通過算法使排序列表的大小變得非常大，那麼在任何給定的遞歸子查詢中對最後十個排序​​的時間將不起作用整體運行時間。