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

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

查看agf here的评论

解决方法

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

更多详细信息(来自于Stack Overflow上的other questions,以及Python源代码中的一些内容)：

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

如果您想自己玩这些命令,可以将这些命令粘贴到您的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,'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,'a = 3; b = 400')
show_timeit('math.pow(a,'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,'a = 3.; b = 400.')
show_timeit('math.pow(a,'import math; a = 3.; b = 400.')

（编辑：甘南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!