面试经典150题 P50 Pow(x, n)

---

时间轴

时间轴

2025-11-26

init

数学

---

题目：

如果直接循环n次，时间是O(n)，会超时。利用快速幂：

快速幂基于一个事实：

• 如果 n 是偶数：

  $$x^n = (x^2)^{n/2}$$

• 如果 n 是奇数：

  $$x^n = x \cdot x^{n-1}$$

每次把 n 减半，因此时间复杂度是O(log n)。

class Solution {
    public:
	double myPow(double x, int n)
	{
		// 快速幂
		long pow = (long)n;
		if (pow < 0) {
			x = 1 / x;
			pow = -pow;
		}

		double res = 1;
		while (pow > 0) {
			if ((pow & 0x1) == 0) {
				x = x * x;
				pow = pow / 2;
			} else {
				res *= x;
				pow = pow - 1;
			}
		}
		return res;
	}
};