證明QuickSort的最壞情況下運行時間

Question

我試圖對下面的遞歸函數進行漸近分析，以便爲數字提供有效的方法。我無法確定遞推方程，因爲當功率奇數和功率均勻時有不同的方程。我不確定如何處理這種情況。我知道運行時間是theta（logn），所以關於如何繼續這個結果的任何建議將不勝感激。

Recursive-Power(x, n): 
if n == 1 
    return x 
if n is even 
    y = Recursive-Power(x, n/2) 
    return y*y 
else 
    y = Recursive-Power(x, (n-1)/2) 
    return y*y*x 

Answer 1

在任何情況下，用以下條件成立：

T(n) = T(floor(n/2)) + Θ(1) 

其中floor(n)是最大的整數不大於n。

由於floor不會對結果的影響，方程非正式地寫爲：

T(n) = T(n/2) + Θ(1) 

你已經猜到了正確綁定漸近。結果可以用替代方法或主定理來證明。它留給你做練習。