a^b的非回收算法具有log(b)的时间复杂性

Question

有一个项目，我应该实现产生a^b的幂算法（a，b），算法应具有log（b）的复杂性（b是函数中的第二个输入号）以及算法也应无寻常。谁能帮忙？

Answer 1

这个想法是构造正方形所需的乘法

让我们从具体示例开始：7^13

13是二进制中的1101

所以7*((7^2)^2*((7^2)^2)^2)=7^(1+4+8)=7^13

算法：

1. 让x = a，res = 1
2. 从小到主要
   1. 如果当前位比1，res = res*x
   2. x = x*x

时间复杂性与B的数量相同，即log（b）