以下用于求幂的分而治之递归算法是否比大数的迭代算法更有效？

Question

我有以下两种算法。我的分析表明它们都是 O(m^2+4^n) 即它们对于大数是等价的。这是正确的吗？。请注意 m 和 n 是 x 和 y

的位数

def pow1(x, y):

    if y == 0:
        return 1
    temp = x
    while y > 1:
        y -= 1
        temp *= x
    return temp

def pow2(x, y):

    if y == 0:
        return 1
    temp = pow2(x, y//2)
    if y & 1:    return temp * temp * x
    return temp * temp

Answer 1

divide-and-conquer 算法是否更有效取决于很多因素。在 Python 中效率更高。

您的分析是正确的；假设标准 grade-school 乘法，divide-and-conquer 执行更少、更昂贵的乘法，并且渐近地使总运行时间变得很容易（常数因子可能很重要——我仍然猜测 divide-and-conquer 会更快，因为大多数工作是在优化的 C 中而不是在 Python 循环开销中进行的，但这只是一种预感，并且很难测试，因为 Python 不使用基本乘法算法).

在继续之前，请注意 Python 中的大整数乘法是 m^2 的 little-o。特别是，它使用 karatsuba，对于 m-bit 整数和 n-bit 整数，m<=n.

大约为 O(m^0.58 n)

使用普通乘法的小项不会渐近影响，因此关注大项我们可以替换乘法成本并发现您的迭代算法大约为 O(4^n m^1.58) 并且您的 divide-and-conquer 解决方案大约是 O(3^n m^1.58).

以下用于求幂的分而治之递归算法是否比大数的迭代算法更有效？

Is the following divide and conquer recursive algorithm for the exponentiation more efficient than the iterative one for large numbers?

python

python-3.x

time-complexity

big-o

exponentiation