快速冪

快速冪是一種能在$O(\log n)$時間內算出$a^n$的技巧
背後的原理是將次方以二進制表示

舉例來說如果今天你要算$5^{11}$，原本你可能會算$5\times5\times5\times5….$乘到11，做n次。

快速冪則是將式子換成$5^8 \times 5^2 \times 5^1$ 也就是下面這個表格

$2^0$ $2^1$ $2^2$ $2^3$
1 1 0 1

5的次方

換成這種形式的好處是原本要做n次的運算，瞬間就變為$O(\log n)$

程式碼:

方法一:遞迴

1
2
3
4
5
6
7
8
int quickpow(int x, int n) {
  if (n == 0) return 1;
  int res = quickpow(x, n / 2);
  if (n % 2) //基數
    return res * res * x;
  else //偶數
    return res * res;
}

方法二:迴圈

1
2
3
4
5
6
7
8
9
int quickpow(int x, int n) {
  int res = 1;
  while (n > 0) {
    if (n & 1) res = res * x; //  基數
    x = x * x;
    n >>= 1; //  n /= 2
  }
  return res;
}