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

在用python刷题，需要知道幂运算的时间复杂度。我自己其实也大概查了一下
说当写成 pow(X,N) 或 math.pow(X,N) 时, 时间复杂度算作 O(1)
当写成 X**N 时,  时间复杂度算作是 O(logN)
请问以上正确吗??!!!

那幂运算写成 pow(X,N) 会更好些因为时间复杂度低是O(1)?
求谁能清晰回答一下，谢谢各位，解答保证加米



补充内容 (2021-12-27 17:54 +8:00):
亲们，为啥我会问这个呢？事情是这样的。我找实习面试的时候，面试官考了我一个题，其实很简单，就是给你一个string表示十六进制，你要转换成十进制的 int 就好了。然后我就写了下面的代码，然后面试官问我时间复杂度。我就说是O(N)啊，N是输入的string的长度。然后面试官说错了，因为这条语句 answer += value * (16 ** exp) 不是 constant time. 但后我就支支吾吾不知道怎么回答了，就挂了。  所以我只要写成 answer += value * pow(16, exp) 就算 constant time了？？我真不知道咋分析时间复杂度


class Solution:

    def HexToDecimal(self, Hex: str) -> int:
        is_valid_hex = True
        answer = 0
        exp = 0
        N = len(Hex)

        for i in range( N-1, -1, -1):
            char = Hex
            if '0' <= char <= '9':
                value = ord(char) - ord('0')
            elif 'a' <= char <= 'f':
                value = ord(char) - 87 # why 87? ord('a') - 87 = 10, ord('a') = 97
            elif 'A' <= char <= 'F':
                value = ord(char) - 55 # why 55? ord('A') - 55 = 10, ord('A') = 65
            else:
                is_valid_hex = False
                break
            answer += value * (16 ** exp)
            exp += 1

        if is_valid_hex:
            return answer
        else:
            # if input is an invalid hexadecimal string, return -1
            return -1

补充内容 (2021-12-27 17:59 +8:00):
纠正  char = Hex 这行应该是 char = Hex【i】

当写成 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 位整数范围的情况下，二者的时间基本没有区别。

摘自stack overflow

pow and ** do integer exponentiation if their arguments are integers. (Python 3 has automatic bignum support, so, for example, a ** b always gives the exact integral result, even if a or b are very large.) This takes O(log(b)) multiplications with exponentiation by squaring, but bignum multiplication isn't constant time, so the time complexity depends on details of the multiplication algorithm used. (Also, Python doesn't quite use exponentiation by squaring, but what Python does use still takes O(log(b)) multiplications.)
math.pow, on the other hand, is different. It always does floating point exponentiation and is always O(1). That O(1) complexity isn't because it's any more efficient than pow or **; it's because floating point sacrifices accuracy and range. For cases where the non-constant complexity of integer exponentiation actually matters, math.pow will give much less precise results or throw an OverflowError

墨绿 发表于 2021-12-27 20:52
代码是对的跟面试官核对过，但我不会分析时间复杂度了。思路把我引导写成了这种代码，肯定也有不用幂运算 ...

你这个从后往前遍历，每次乘n。n初始化为1，每次乘完了以后n*=16就行了啊... 我个人认为这里无论你用**还是pow面试官都会挂你，因为如果面试官不了解python（比如，他常用c++），他根本不会去了解这俩的区别。从显然的角度（或者从c++的角度），pow显然不是常数级别复杂度。

可能pow(x, N)会被写成 e^(N * log(x))，然后被算成某些基础函数取值的复杂度？

1. import math
   
2. import numpy as np
   
3. import time
   
4. 
   
5. 
   
6. nums = np.random.randn(1000000)
   
7. times_pow = []
   
8. times_math = []
   
9. times_op = []
   
10. 
    
11. for num in nums:
    
12.     t = time.time()
    
13.     pow(num, 64)
    
14.     times_pow.append(time.time() - t)
    
15.     t = time.time()
    
16.     math.pow(num, 64)
    
17.     times_math.append(time.time() - t)
    
18.     t = time.time()
    
19.     num ** 64
    
20.     times_op.append(time.time() - t)
    
21. 
    
22. print(np.mean(times_pow))
    
23. print(np.mean(times_math))
    
24. print(np.mean(times_op))
    
25. print(np.mean(times_op) / 6)

复制代码

4.969379901885987e-07
2.6874446868896486e-07
4.787726402282715e-07
7.979544003804525e-08

babybear68 发表于 2021-12-26 20:40
4.969379901885987e-07
2.6874446868896486e-07
4.787726402282715e-07

没太看懂这想表达什么意思……

newcodingfarmer 发表于 2021-12-26 20:41
摘自stack overflow

pow and ** do integer exponentiation if their arguments are integers. (Python 3  ...

您的这个我看过了呢，所以这就是 a**b 时间复杂度算 O(logb)，pow(a,b)的话算O(1) 咯？

小小程序媛 发表于 2021-12-26 23:43
没太看懂这想表达什么意思……

意思就是如果pow是O(1)的话 以浮点数为底数的**运算符不太可能是O(log(n))的 以整数为底数的结果类似如下：
3.931338787078857e-07
2.75949239730835e-07
3.785521984100342e-07
6.309203306833904e-08

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

那所以pow(X,N) 和 X**N 的时间复杂度是多少呢……不好意思我基础薄弱，给您加米了……

https://leetcode.com/submissions/detail/604506212/

小小程序媛 发表于 2021-12-27 00:03
那所以pow(X,N) 和 X**N 的时间复杂度是多少呢……不好意思我基础薄弱，给您加米了……

我觉得具体是多少不是很重要 只需要知道三者的复杂度应该是一样的就可以 在做题的时候随便用哪一个 面试的时候最好写** 因为比较简洁易读 实际的复杂度可能和底层代码甚至硬件加速有关 除非面试的是相关的岗位 不太可能会问到你这个问题 甚至面试官都不一定清楚有什么区别 你给出的解的复杂度可以理解为进行多少次幂运算 比如说O(n^2)次幂运算 而幂运算具体的复杂度和你给出的解没什么关系 比如说你的解可以进一步优化到O(n*log(n))次幂运算 都是以一次幂运算当作计量单位的 如果可以以比如说加法运算当作计量单位 那说明你的解法可能有问题