現有一個數x和n，如何用儘可能少的操作算出x的n次方？（每次加減乘除算一次操作，且可以認為n挺大的）?

---

Addition-chain exponentiation

---

int pow(int x, int n) //快速冪
{
int res = 1;
while(n)
{
if(n 1) res *= x;
x *= x;
n &>&>= 1;
}
return res;
}


---

1把n轉成2進位數，假設這個二進位數有k位

2通過不斷平方，算出x^1, x^2, x^4......x^(2^k)

3把二進位數對應的x指數相乘，如果二進位數的第i位是1, 則乘以x^(2^i)，得到結果

這種演算法經常被用來計算x^n mod k, 空間複雜度是O(klgn)

---

上面的答案時間複雜度是最優的，但空間不是。要麼顯式存了x^i, 要麼用了遞歸(非尾遞歸)額外消耗了O(lgn)的棧空間。

int fast_exp(int x, int n){
int r = 1;
while(n&>0){
if(n%2 == 0){
x = x*x;
n /= 2;
} else {
n -= 1;
r *= x;
}
}
return r;
}


循環不變數

時間O(lg n), 空間O(1)

---

def exp(x ,n):
if n == 0:
return 1
if n % 2 == 0:
return exp(x * x, n // 2)
else:
return x * exp(x, n - 1)
#時間複雜度O(logn) 遞歸深度O(logn)..還是非遞歸好=_3


---

(define (power base exp)
(cond ((= exp 0) 1)
((= exp 1) base)
((even? exp) (square (power base (/ exp 2))))
(else (* base (power base (- exp 1))))))

;;; 感覺和頂樓說的轉成二進制也沒打的區別？


---

推薦閱讀：