在计算算法的效率时，我读到求幂运算不被视为原子运算(如乘法)。
是因为乘幂运算与重复多次的乘法运算相同吗？
最佳答案
原则上，您可以对您认为需要单个时间单位进行评估的数字选择任何“核心”操作集。然而，有几个原因导致我们通常不将求幂算作其中之一。
也许最大的问题与您产生的输出量有关。假设您有两个数字 x 和 y，每个数字的长度均为 d 位。那么它们的和 x + y 有(最多) d + 1 位数字 - 只比我们开始的大一点。他们的乘积 xy 最多有 2d 位数字——比我们开始时的数字大，但也不是很大。另一方面，值 xy 大约有 yd 位，这可能比我们开始时要大得多。 (一个很好的例子:考虑计算 100100，大约有 200 位数字!)这意味着简单地写下求幂的结果将需要相当多的时间才能完成。
这并不是说您不能将求幂视为常数时间运算。相反，我只是从未见过它被完成。
(有趣的事实:一些理论论文不认为乘法是一个恒定时间运算，因为乘以两个 b 位数字的硬件电路的复杂性随着 b 的大小呈二次方增长。并且一些理论论文不认为乘法是一个常数时间运算。也不要认为加法是恒定时间的，尤其是在处理可变长度数字时!这一切都与上下文有关。如果您正在处理适合机器单词的“小”数字，那么我们可以轻松地将加法和乘法计算为花费恒定的时间。如果您有巨大的数字 - 例如，用于 RSA 加密的大素数 - 那么数字的大小开始影响算法的运行时间和实现。)
关于algorithm - 为什么求幂不是原子的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/73840440/