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

前端之家收集整理的这篇文章主要介绍了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函数,它总是进行浮点数学运算. (见herehere.)这通常更快,但不准确.有关可能实施pow的一种方法,请参见here.
>对于浮点数,pow / **也调用C库的pow函数,所以没有区别.见herehere.

如果您想自己玩这些命令,可以将这些命令粘贴到您的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.')

猜你在找的Python相关文章