performance - Power 操作的时间效率？

Question

我只是想知道电源操作及其时间效率。由于幂运算是有效的：

x^n = x*x*x...[n times]

这是否意味着计算 x^n 大约需要 O(n) 时间（假设乘法是 O(1)，我不确定是不是这样）？或者现代编程语言/硬件架构是否有优化，可以将其减少到 O(1) 或类似的东西？如果存在优化，请解释（或发布解释链接）。

Answer 1

有一个基于连续平方的优化，允许您以对数乘法计算幂。例如，不是将 b ⁸计算为 b*b*b*b*b*b*b*b，而是可以计算

b ² = b * b
b ⁴ = b ² * b ²
b ⁸ = b ⁴ * b ⁴

有关详细信息，请参阅SICP 1.2.4 求幂。我的博客上也有一篇文章，展示了Scheme 中的快速求幂实现。