>>68 ありがとうございます。 a.は擬似コード見つけました。 FastPower(a; n): if n = 1 return a else x FastPower(a; bn=2c) if n is even return x * x else return x * x * a
The total number of multiplications is given by the recurrence T(n) <= T(L n/2 」) + 2, with the base case T(1) = 0. After a domain transformation, the Master Theorem gives us the solution T(n) = O(log n). Incidentally, this algorithm is asymptotically optimal|any algorithm for computing an must perform (log n) multiplications.
