指数算法分析

Question

本文提供了关于指数的如下内容

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

特别是

，一个200位数字被提升到一个大的幂(通常是另一个200位数)，在每次乘法后只保留200位左右的数字。由于计算需要处理200位数，所以效率显然是很重要的.直截了当的指数算法需要大约10到200次乘法，而递归算法只需要大约1,200次。

关于上面的问题，我的问题1。对于简单算法和递归算法，作者是如何得到10到200倍的乘法的？作者是如何带着上面的数字来的，谢谢！

Answer 1

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

Answer 2

指数有200位数，因此它大约是10到200的幂。如果使用朴素指数，你将不得不做这个数量的乘法。

另一方面，如果使用递归指数，乘法的次数取决于指数的位数。由于指数几乎是10^200，所以它有log(10^200) = 200*log(10)位。这是600，其中的2来自一个事实，如果你有1位，你必须做两个乘法。

Answer 3

以下是两种可能的算法：

algo给出一个^N

SimpleExp(a,N):
   return a*simpleExp(a,N-1) 

这是N个运算，所以对于^( 10^200 )是10^200

OptimizedAlgo(a,N):
      if N == 0:
                 return 1
      if (N mod 2) == 0:
                return OptimizedAlgo(a,N/2)*OptimizedAlgo(a,N/2)  // 1 operation
      else:
                return a*OptimizedAlgo(a,(N-1)/2)*OptimizedAlgo(a,(N-1)/2)  //2 operations

对于a^(10^200)，在log2(N)和2* log2(N)操作(2^(log2(N) =N)之间)

和log2(10^200) = 200 * log2(10) ~ 664.3856189774724

2*log2 2(10^200) =1328.771237954945

，所以操作的数量在664到1328之间。