クイックソートの最悪の実行時間を証明する

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

、次の条件が成立する：

floor(n)が nより大きくない最大の整数である

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

を。

floorが結果に影響を与えないので、式は非公式のように書かれている：あなたは正しくバインドさ漸近的に推測している

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

。その結果は、Substitution法またはMaster定理を用いて証明することができた。それはあなたのための練習として残されています。