復發關係快速排序

Question

我一直在尋找快速排序的復位關係，我可以按照他們如何得到最終的復發關係，但他們跳轉到時間順序。例如：

T(N) = T(N-1) + T(0)+ Theta(sqrt(N)) 

然後，他們跳的時間順序：O(Nsqrt(N))

我不跟着他們從遞推關係的時間順序是怎麼...

Answer 1

的遞推關係沒有明確定義。你需要一個邊界條件。我們假設T(1)=1=sqrt(1)和T(0)=0。

的事實T(N)=O(N*sqrt(N))是很容易證明：

T(N) = T(N-1) + Theta(sqrt(N)) = T(N-2) + sqrt(N-1) + sqrt(N) 
    = ... = sqrt(N) + sqrt(N-1) + ... + sqrt(1) 
    <= N * sqrt(N). 

的束縛<= N*sqrt(N)顯然成立是因爲sqrt(1)<...<sqrt(N-1)<sqrt(N)。

因此T(N)=O(N*sqrt(N))。