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.')

相关文章

在这篇文章中,我们深入学习了XPath作为一种常见的网络爬虫技巧。XPath是一种用于定位和选择XML文档中特...
祝福大家龙年快乐!愿你们的生活像龙一样充满力量和勇气,愿你们在新的一年里,追逐梦想,勇往直前,不...
今天在爬虫实战中,除了正常爬取网页数据外,我们还添加了一个下载功能,主要任务是爬取小说并将其下载...
完美收官,本文是爬虫实战的最后一章了,所以尽管本文着重呈现爬虫实战,但其中有一大部分内容专注于数...
JSON是一种流行的数据传输格式,Python中有多种处理JSON的方式。官方的json库是最常用的,它提供了简单...
独立样本T检验适用于比较两组独立样本的均值差异,而配对T检验则适用于比较同一组样本在不同条件下的均...