首页 > 试题广场 >

求一个数x的n次方最朴素的方式是在1的基础上乘n次x，如果用

[单选题]

求一个数x的n次方最朴素的方式是在1的基础上乘n次x，如果用递归，显然会执行n次递归函数，时间复杂度为O(N)。不过可以通过对n的奇偶性判断来加大递归步长，每次可将范围减半，即如果n是偶数，那么x^n = x^(n/2) * x^(n/2)，下面的函数是实现了这个过程的完整代码，它的时间复杂度为（）

int pow(int x, unsigned int n)
{
    if (n == 0)
        return 1;
    if (n & 1)
        return pow(x, n / 2) * pow(x, n / 2) * x;
    else
        return pow(x, n / 2) * pow(x, n / 2);
}

```
O(logN)
```
```
O(N)
```
```
O(N*log(N))
```
```
O(N^2)
```

查看正确选项

WonderWu

该算法的思想是将一个数根据奇偶性分别进行不同的算法规模的降低，将n降低到n/2

使用递归公式法分析复杂度：

时间复杂度的递归通项为：T（n）= 2T（n/2）+ O（1）

其中，由于将复杂度为n的问题拆解为两个规模为n/2的子问题，所以乘2，O(1)为相乘和加一的操作

推演过程：
T（n）= 2T（n/2）+ O（1）
      = 4T（n/4） + 3 O（1）
      = 8T（n/8）+ 7 O（1） 
      ……（中间省略）
      = 2^k * T（n/2^k） + （2^k - 1）*O（1）

当 n/2^k = 1 时有返回值，此时结束递归，即2^k = n ,k = log2(n)

代入上述式子，得 
T（n）= n*O（1） + （n - 1）*O(1)
      = O（n）

另外：

通过减半操作的确能加速，不过代码中重复计算了pow(x, n / 2)，如果将其结果保存到一个变量，return语句改为变量相乘，复杂度将骤降到O(logN)。

编辑于 2024-02-06 16:15:05 回复(0)