algorithm - 俄罗斯农民乘法算法的时间效率

Question

从时间效率的角度来看，俄罗斯农民乘法算法是用 n 乘 m 还是 m 乘 n 有关系吗？

比如计算26*47时，时间效率和计算47*26差不多吗？

标签： algorithmlanguage-agnostic

Answer 1

由于该算法floor(log2(k))针对 的乘数（第一个数字）运行迭代k，因此运行时间肯定取决于顺序。如果n和m位于两个相同的两个连续幂之间，那么它们将需要相同数量的迭代来完成。否则，请始终将较小的数字放在第一位以最小化运行时间。