为什么Pow(x,y)的时间复杂度为O(1),而x**y为O(n)？

Question

为什么时间复杂度为O(1)pow(x,y)而O(n)为x ** y？

在这里查看来自agf的 评论

Answer 1

声明是错误的.

• pow或多或少相同**.
• pow**如果参数是整数,则进行整数取幂.(Python 3具有自动bignum支持,因此,例如,a ** b即使a或b非常大,也总是给出精确的积分结果.)这需要通过平方乘以取幂的O(log(b))乘法,但是bignum乘法不是' t恒定时间,因此时间复杂度取决于所使用的乘法算法的细节.(另外,Python并没有通过平方来使用取幂,但Python使用的仍然需要O(log(b))乘法.)
• math.pow另一方面,则有所不同.它总是进行浮点求幂,并且始终为O(1).O(1)的复杂性不是因为它比powor 更有效**; 这是因为浮点牺牲了准确性和范围.对于整数求幂的非常数复杂度实际上很重要的情况,math.pow将给出更不精确的结果或抛出一个OverflowError.

更多详细信息(从回顾Stack Overflow上的其他 问题,以及在Python源代码中进行了一些讨论):

• pow(见这里)和**(见这里)都调用相同的PyNumber_Power功能.在实践中,**可以更快,因为它避免了额外的符号查找和函数调用的开销.
• pow/ 的整数实现**可以在这里看到.
• math.pow另一方面,总是调用C库的pow函数,它总是进行浮点数学运算.(见这里和这里.)这通常更快,但不准确.请参阅此处了解pow可能实施的一种方法.
• 对于浮点数,pow/ **也调用C库的pow函数,所以没有区别.看到这里和这里.

如果您想自己玩这些命令,可以将这些命令粘贴到您的IPython会话中:

import timeit

def show_timeit(command, setup):
    print(setup + '; ' + command + ':')
    print(timeit.timeit(command, setup))
    print()

# Comparing small integers
show_timeit('a ** b', 'a = 3; b = 4')
show_timeit('pow(a, b)', 'a = 3; b = 4')
show_timeit('math.pow(a, b)', 'import math; a = 3; b = 4')

# Compare large integers to demonstrate non-constant complexity
show_timeit('a ** b', 'a = 3; b = 400')
show_timeit('pow(a, b)', 'a = 3; b = 400')
show_timeit('math.pow(a, b)', 'import math; a = 3; b = 400')

# Compare floating point to demonstrate O(1) throughout
show_timeit('a ** b', 'a = 3.; b = 400.')
show_timeit('pow(a, b)', 'a = 3.; b = 400.')
show_timeit('math.pow(a, b)', 'import math; a = 3.; b = 400.')