递归效率与指数迭代的效率

Question

所以我试图实现一种更有效的计算方法2^n.

我知道你可以拆分它以便O(logn)它可以很容易地使用递归.你继续除以2,然后乘以奇数(或类似的东西)时的较低功率.问题是我用手写出了我的乘法方法,因为它的数字很大.所以它需要返回多个参数.

我能想到的一个解决方案是创建一个包含所有必需信息的对.除此之外我虽然试图弄清楚如何使用迭代来编写它.我能看到的唯一方法是使用某种数据结构,然后循环将n除以2,并在n为奇数时存储该值.然后编写for循环并在每次迭代时检查该值是否包含在数据结构中.在我看来,这似乎是一个相对昂贵的操作.

是否有可能最终效率低于递归版本？

我这样做是因为:

1. 我不能让gnp工作.
2. 我想我正在学习编写大数字课程并使用它.

Answer 1

如果你打算使用大数字,而不是重新发明轮子,你可能应该看一下GNU MP Bignum Library.

关于递归与迭代问题,答案是你总是可以把它们写成等价的; 只调用自身作为尾调用的递归函数与while循环一样高效(前提是您的编译器支持尾调用优化,但最常见的编译器会这样做).例如,您正在描述的快速取幂函数的尾递归版本是(伪代码):

function fastExp(base, exponent, accumulator) {
  if(exponent == 0) {
    return accumulator;
  } else if(exponent % 2 == 0) {
    return fastExp(base * base, exponent/2, accumulator);
  } else {
    return fastExp(base, exponent-1, base * accumulator); 
  }
}

将这个递归函数看作循环,其中循环条件是exponent != 0,并且递归调用类似于goto循环开始的s.(accumulator = 1顺便说一句,你需要在开始时调用它.)它等同于以下内容:

function fastExp(base, exponent) {
  var accumulator = 1;
  while(exponent != 0) {
    if(exponent % 2 == 0) {
      base *= base;
      exponent /= 2;
    } else {
      exponent -= 1;
      accumulator *= base;
    }
  }
  return accumulator;
}

因此,您可以看到它们是等效的,因此将执行相同数量的操作.