求 pow(x,n) 先来说说快速幂,正常的做法线性速度,O(n)的时间复杂度。快速幂的时间的复杂度O(log2(n))
其数学推导如下:
当n为偶数时 若2k = n 即k = n/2 则x^(2k) = x^(k)x^(k);
当n为奇数时 若2k+1=n 即k = n/2 则x^(2k+1) = x^(k)x^(k)*x;
递归结束条件 : n = 0 return 1.0
这里还需注意一下 n可能为正 也可能为负
具体程序 见代码:
而对于快速幂取模。求(a^n)%M
对于求模,有个很关键的公式 (ac)%m = (a%m)(c%m)%m
同时呢: (a+d)%m = ((a%m)+(d%m))%m
数学推导如下:
若n为偶数: 假设 n = 2k (a^2k)%m = ((a^k)%m)((a^k)%m)%m
若n为奇数: 假设 n = 2k+1 (a^(2k+1))%m = (((a^k)%m(a^k)%m)%m*a%m)%m
递归结束条件 : n = 0 return 1.0
具体程序见代码:
递归方法 method1:
递归 method2