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

Question

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

请参考这里来自agf的评论。

- Kumar Tanmay

---

你说得对 - 那听起来不准确。（这来自 unseen_rider 的评论。） - Ry-

希望我能在那里评论并询问他们两个 :-) - Kumar Tanmay

那个评论毫无意义。对于一个整数 n，pow(n, 0.5) 和 n ** 0.5 都会简单地调用底层的 C 库函数 pow。（就我个人而言，我会每次都选择使用 sqrt：它更有可能正确地四舍五入，并且不太可能比 pow 或 ** 慢得明显。） - Mark Dickinson

@RunOrVeith: 只有在你想进行浮点数指数运算时，pow(x, y) 对于 int 值才更快，但它们仍然具有相同的时间复杂度。 - Ry-

@KumarTanmay 当模数为1时，结果将始终为0。因此，首先计算一个大数，然后在最后返回0意味着您必须将该大数存储在内存中直到结束。如果您一路上使用0进行模运算，您将永远无法达到那个大数，而只会在内存中存储0。 - sepp2k

Answer 1

声明是错误的。

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

更多细节（从审核other questions on 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.')

- Josh Kelley