为什么pow（x，y）的时间复杂度为O（1），而x ** y的时间复杂度为O（n）？ [英] Why is time complexity O(1) for pow(x,y) while it is O(n) for x**y?

问题描述

为什么时间复杂度O（1）为 pow（x，y）而时间复杂度为O（n）的 x ** y ？

Why is time complexity O(1) of pow(x,y) while it is O(n) for x ** y?

从 agf 查看评论此处

推荐答案

该语句是错误的。

• 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 。

• pow is more or less identical to **.
• 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.

更多详细信息（通过查看其他 关于堆栈溢出的问题，以及从Python源中抽出一点时间）：

Further details (from reviewing other questions on Stack Overflow, and from poking a bit at the Python source):

• pow （请参阅此处）和 ** （请参见此处）都调用相同的 PyNumber_Power 函数。实际上， ** 可以更快，因为它避免了额外的符号查找和函数调用的开销。


• 整数实现战俘 / ** 的此处。


• math.pow 总是调用C库的 pow 函数，始终执行浮点数学运算。 （请参见此处和此处。）这通常更快，但并不精确。请参阅此处，以了解可以实现 pow 的一种方式。


• 对于浮点数， pow / ** 也称为C库的 pow 函数，所以没有区别。请参见此处和此处。

• pow (see here) and ** (see here) both call the same PyNumber_Power function. In practice, ** can be faster, because it avoids the overhead of an extra symbol lookup and function call.
• The integer implementation of pow / ** can be seen here.
• math.pow, on the other hand, always calls the C library's pow function, which always does floating point math. (See here and here.) This is often faster, but it's not precise. See here for one way that pow might be implemented.
• For floating point numbers, pow / ** also call the C library's pow function, so there's no difference. See here and here.

如果您想自己玩，可以将以下命令粘贴到IPython会话中：

You can paste these commands into your IPython session if you want to play with this yourself:

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

这篇关于为什么pow（x，y）的时间复杂度为O（1），而x ** y的时间复杂度为O（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！