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

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)

漸近境界を正しく推測しました。結果は、置換法またはマスター定理を使用して証明できます。それはあなたのための練習として残されています。