时间轴

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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
	}
};