我該如何證明quicksort的主定理

Question

我有一個關於算法quicksort的問題。 有人可以解釋我如何得到結果（證明）2T（n/2）+Θ（n）？ 而這個結果意味着：T（n-1）+Θ（n）。

感謝您的所有答案。

Answer 1

主定理指出，

對於任何，

1. 如果對於某一常數，然後。
2. 如果，則。
3. 如果，對於某一常數，如果對於某一常數和所有足夠大，然後

至於你，
，

這裏，
（第二種情況）
所以複雜度將是：

對於第二個問題，要了解此功能，您需要了解分治法。在快速排序中，對於n如果您將最後一個值作爲關鍵點，則項目數將減少，這會將項目數減少到（n-1），現在如果遞歸調用快速排序將最後一個值作爲關鍵點，每次減少一個項目。因此，複雜性將是，當您將中間值作爲中心時，情況並非如此。