快速幂算法

快速幂算法可用分治法实现

不难看出，对任意实数a和非负整数n，有：
$$a^n=\{\begin{array}{ll}1,& n=0,a\ne 0\\ 0,& a=0\\ {\left(a^{\frac{n}{2}}\right)}^2,& n>0,n\text{为偶数}\\ {\left(a^{\frac{n}{2}}\right)}^2\ast a,& n>0,n\text{为奇数}\end{array}$$
这里n/2是C语言中的整除计算，所以n为奇数时需要额外乘一个a
n=0可作为递归边界

递归实现

• a如果等于0则返回0

• n=0时作为递归边界返回1

• n不等于0时，递归求$a^{\frac{n}{2}}$的值，再根据n的奇偶性返回相应值

代码

double exp2(int a, int n){if (a == 0)return 0;if (n <= 0)return 1;else{int x = exp2(a, n/2);if (n % 2)return x * x *a;return x * x;}
}

时间复杂度为O(logn)

非递归实现

非递归实现的方法在于将指数n分解乘二进制，将对应二进制位为1的乘起来，就得到最终的结果

例：计算$3^{93}$

$93=(1011101{)}_2=64+16+8+4+1$

$3^{93}=3^{64}\ast 3^{16}\ast 3^8\ast 3^4\ast 3$

代码

• 变量s存储当前计算结果，并最终作为返回值

• 变量b存储当前数位的乘方值

• 遍历n的每一个二进制位

  • n & 1判断指数当前的最后一位是否为1
  • 每次循环将指数n右移一位（除以2），并将b累乘一次，计算当前的乘方

double exp2(int a, int n) {double b, s = 1.0;b = a;while (n > 0) {if (n & 1) {s *= b;}n /= 2;b *= b;}return s;
}

因为n有logn+1个二进制位，只需要次计算就能得到$a^n$，时间复杂度为O(n)

测试

double exp2(int a, int n) {double b, s = 1.0;b = a;while (n > 0) {if (n & 1) {s *= b;}n /= 2;b *= b;}return s;
}
int main()
{cout << exp2(3, 93);return 0;
}

结果

结果正确

由于递归算法涉及到对栈的操作，一般建议使用非递归算法