[算法]程序员必学：快速幂算法( 三 ) |程序员|计算复杂性理论|高德纳|

第7行代码

x = (3 ^ 4) * (3 ^ 4) = (3 ^ 8)

第8行代码

n右移1位，其二进制变成了10（对应的十进制是啥？不重要！！！）

------第4轮while循环-----

第4行代码

n的二进制是10
x = 3 ^ 8, 其对应二进制位的值是0（n的最后一个二进制位）
所以不需要执行第5行代码

不需要将x乘进最终结果
result = (3 ^ 1) * (3 ^ 4)

第7行代码

x = (3 ^ 8) * (3 ^ 8) = 3 ^ 16

第8行代码

n右移1位，其二进制变成了1（对应的十进制是啥？不重要！！！）

------第5轮while循环-----

第4行代码

n的二进制是1
x = 3 ^ 16, 其对应二进制位的值是1（n的最后一个二进制位）
所以需要执行第5行代码

将x乘进最终结果
result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)

第7行代码

x = (3 ^ 16) * (3 ^ 16) = 3 ^ 32

第8行代码

n右移1位，其二进制变成了0

------最后-----

由于n = 0 ，所以退出while循环

最终result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)

复杂度分析

每执行一次while的循环体， n >>= 1, 会导致n的值减半
所以时间复杂度：O(logn)、空间复杂度：O(1)

Leetcode Leetcode上的第50号题50.Pow(x, n) ，刚好就可以用今天讲解的快速幂算法。以下是我的代码实现

// 递归 double myPow(double x, int n) {if (n == 0) return 1;if (n == -1) return 1 / x;double half = myPow(x, n >> 1);half *= half;return ((n & 1) == 1) ? half * x : half;}// 非递归double myPow(double x, int n) {long y = (ndouble result = 1.0;while (y > 0) {if ((y & 1) == 1) {result *= x;}x *= x;y >>= 1;}return (n }

【[算法]程序员必学：快速幂算法】需要提醒的是