algorithm - 指数算法分析

Question

下面的文字是关于求幂的

我们有明显的算法来计算 X 的 N 次幂使用 N-1 次乘法。递归算法可以做得更好。 N<=1 是递归的基本情况。否则，如果 n 是偶数，我们有 xn = xn/2 。 xn/2，如果 n 是 奇数，x 的 n 次方 = x(n-1)/2 x(n-1)/2 x。

Specifically, a 200-digit number is raised to a large power (usually another 200-digit number), with only the low 200 or so digits retained after each multiplication. Since the calculations require dealing with 200-digit numbers, efficiency is obviously important. The straightforward algorithm for exponentiation would require about 10 to power of 200 multiplications, whereas recursive algorithm presented requires only about 1,200.

我对以上文字的疑问1. 对于简单算法和递归算法只有大约 1, 200，作者如何得出 10 的 200 次方乘法？作者如何得出上述数字谢谢!

Answer 1

因为第一个算法的复杂度是线性的，而第二个算法的复杂度是对数的(由于 N)。200 位数字约为 10^200，log_2(10^200) 约为 1,200。