本文共 1571 字，大约阅读时间需要 5 分钟。

【题目描述】

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

【解题思路】

• 求 xⁿ，最简单的方法是通过循环将 n 个 x 乘起来，依次求 x¹, x², …, x^n-1, xⁿ，时间复杂度为 O(n)。
• 快速幂法 可将时间复杂度降低至 O(log₂n)，以下从 “二分法” 和 “二进制” 两个角度解析快速幂法。

• 向下整除 n//2 等价于 右移一位 n>>1 ；
• 取余数 n%2 等价于 判断二进制最右一位值 n & 1 ；

【算法流程】

1. 当 x = 0 时：直接返回 0 （避免后续 x = 1 / x 操作报错）；
2. 初始化 res = 1 ；
3. 当 n < 0 时：把问题转化至 n≥0 的范围内，即执行 x=1/x ，n = - n；
4. 循环计算：当 n = 0 时跳出；
   1. 当 n&1=1 时：将当前 x 乘入 res （即 res∗=x ）；
   2. 执行 x = x²（即 x *= x ）；
   3. 执行 n 右移一位（即 n>>=1）。
5. 返回 res。

class Solution:    def myPow(self, x: float, n: int) -> float:        if x == 0:         	return 0        	        res = 1                if n < 0:         	x, n = 1 / x, -n        	        while n:            if n & 1:             	res *= x            x *= x            n >>= 1        return res'''作者：jyd链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/'''

复杂度分析：

• 时间复杂度 O(log₂n)： 二分的时间复杂度 是对数级别。
• 空间复杂度 O(1) ： res, b 等变量占用常数大小额外空间。

【打印版】

class Solution:    def myPow(self, x: float, n: int) -> float:        if x == 0:             return 0        res = 1 # res保留最终结果        if n < 0:             x, n = 1 / x, -n        while n:            print("x =",x,end='\t')            print("n =",n)            print('n&1=',n & 1,end='\t')            if n & 1:       # 不为0 就是奇数                res *= x    # res先保留多出的一项                print("n是奇数")                print("res =",res)            else:                print("n是偶数")            x *= x            n >>= 1            print()        return ress = Solution()print(s.myPow(3,5))

转载地址：http://rfjii.baihongyu.com/