performance - 在 O(n) 时间内运行的指数乘法算法？

Question

我正在阅读一本算法教科书，但我被这个问题难住了:

假设我们要计算值 x^y，其中 x 和 y 是正数分别具有 m 和 n 位的整数。解决该问题的一种方法是对 x 执行 y - 1 次乘法。你能给出一个仅使用 O(n) 次乘法步骤的更高效的算法吗？

这会是一个分而治之的算法吗？ y-1 乘以 x 将在 theta(n) 中运行，对吗？ .. 我不知道从哪里开始问这个问题

Answer 1

我以迭代的方式更好地理解了这一点:

您可以计算所有 2 的幂的 x^z:z = (2^0, 2^1, 2^2, ... ,2^(n-1))

只需从 1 到 n 并应用 x^(2^(i+1)) = x^(2^i) * x^(2^i)。

现在您可以使用这 n 个值来计算 x^y:

result = 1
for i=0 to n-1:
    if the i'th bit in y is on:
        result *= x^(2^i)
return result

一切都在 O(n) 中完成