算法-快速幂
实现 pow(x, n) ,即计算 x 的 n 次幂函数.(出自力扣)
-100.0 < x < 100.0
n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] .
看到这个题目第一眼想到的就是暴力求解.但也有些疑惑感觉有陷阱...但也没发现问题所在,就暴力一把提交了,发现当指数太大时时间就超时了...
快速幂
快速幂是一种计算一个数的n次方的算法,其时间复杂度为O(log n),暴力求解时间复杂度为O(n).
算法描述
计算an=a * a * a * ... * a,共相乘n次.根据数学公式am+n=am * an,将取幂的任务按照== 二进制表示 ==拆分成更小的任务,举个例子:
计算