我正在读一本算法教科书，我被这个问题难住了：
假设我们要计算值 x^y，其中 x 和 y 为正数
分别具有 m 和 n 位的整数。解决该问题的一种方法是执行 y - 1 乘以 x。你能给出一个仅使用 O(n) 乘法步骤的更有效的算法吗？
这会是一个分而治之的算法吗？ y-1 乘以 x 可以在 theta(n) 中运行，对吗？ ..我不知道从哪里开始问这个问题
我通过迭代的方式更好地理解了这一点：
您可以计算所有 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) 内完成
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
