巨困惑! Python幂运算X**N 和 pow(X,N) 的时间复杂度到底算多少？解答加米!!!

首先，Stack Overflow 上的回答[1]挺详细了，他分情况回答了，而且给出了 Python 源代码的链接。

其次，比较好奇你在什么时候需要计算这么底层的复杂度。

1. https://stackoverflow.com/questi...ile-it-is-on-for-xy

当写成 pow(X,N) 或 math.pow(X,N) 时, 时间复杂度算作 O(1)

基本正确。math.pow 的参数会被转换成 double，然后传进标准库里的 pow 函数。根据 CPU 的不同，这个 pow 函数可能会被转换成一个计算 log 的指令，或者用多项式来拟合，运行时间一般与输入无关。

当写成 X**N 时,  时间复杂度算作是 O(logN)

半对。根据 X 和 N 的数据类型不同，X**N 有两种实现。float 版本的会用标准库里的 pow 函数，和上面差不多。整数版本的会用快速幂算法，在结果不超过 32 位整数取值范围的情况下是 O(log N)。如果结果太大，就会涉及大整数计算，会更慢。

那幂运算写成 pow(X,N) 会更好些因为时间复杂度低是O(1)?

看情况。标准库里的 pow 函数快，是因为用了有误差的拟合函数，而且 double 也是有精度损失的。快速幂可以保证结果完全准确，没有误差，而且 O(log N) 也足够好了（像 4294967296 这么大的数取 log 以后只有 32）。在我的电脑上测试，结果不超过 32 位整数范围的情况下，二者的时间基本没有区别。

helloworld27 发表于 2021-12-26 22:16
基本正确。math.pow 的参数会被转换成 double，然后传进标准库里的 pow 函数。根据 CP ...

太太太感激了！大神！

jcyin100 发表于 2021-12-26 21:18
https://leetcode.com/submissions/detail/604506212/

亲，您给的链接打开是 Page Not Found

databaseinterna 发表于 2021-12-26 21:25
首先，Stack Overflow 上的回答[1]挺详细了，他分情况回答了，而且给出了 Python 源代码的链接。

其次，比 ...

这个我看过了呢，不过还是没理解太清楚，才发帖子问的，谢谢你了噢

小小程序媛 发表于 2021-12-26 23:55:49
这个我看过了呢，不过还是没理解太清楚，才发帖子问的，谢谢你了噢

不客气，其实那个回答挺全了，比目前这里的的回答都全面。你哪里不懂可以贴出来。最终的结论是需要分情况讨论的，像那个回答里面提到的，** 可能还会比 pow 快一点，因为少了一次 symbol lookup 和 function call（要理解这个，你需要了解一点 Python 字节码）。

如果你不是做底层优化的或者本身对这方面就很感兴趣，而是只是为面试时计算复杂度准备的话，我感觉你可能有点儿走偏了。

babybear68 发表于 2021-12-26 20:56:51
意思就是如果pow是O(1)的话 以浮点数为底数的**运算符不太可能是O(log(n))的 以整数为底数的结果类似如下：
3.931338787078857e-07
2.7594923973083

thanks, but why did you divide the ops time by 6 at the end?

databaseinterna 发表于 2021-12-27 00:36
不客气，其实那个回答挺全了，比目前这里的的回答都全面。你哪里不懂可以贴出来。最终的结论是需要分情况 ...

唉，我不知道我走偏没，因为我遇到的问题好像确实需要明白这个。为啥我会问这个呢？事情是这样的。我面试的时候，面试官考了我一个题，其实很简单，就是给你一个string表示十六进制，你要转换成十进制的 int 就好了。然后我就写了代码(贴图了)，然后面试官问我时间复杂度。我就说是O(N)啊，N是输入的string的长度。然后面试官说错了，因为这条语句 answer += value * (16 ** exp) 不是 constant time. 但后我就支支吾吾不知道怎么回答了，然后我就挂了。  所以我只要写成 answer += value * pow(16, exp) 就算 constant time了？？不然我真不知道咋分析时间复杂度了。

小小程序媛 发表于 2021-12-27 01:48:35
唉，我不知道我走偏没，因为我遇到的问题好像确实需要明白这个。为啥我会问这个呢？事情是这样的。我面试的时候，面试官考了我一个题，其实很简单，就是给你一个string表示十六进制，你要转换成十进制的 in

你的问题应该是不需要 pow 运算。

databaseinterna 发表于 2021-12-27 03:19:56
你的问题应该是不需要 pow 运算。

代码是对的跟面试官核对过，但我不会分析时间复杂度了。思路把我引导写成了这种代码，肯定也有不用幂运算的解😔法但我不会了呢