时间戳

首页 > 解决方案 > 迭代与递归的大 O 区别是什么？

javascript - 迭代与递归的大 O 区别是什么？

问题描述

迭代与递归的大 O 区别是什么？为什么运行时间如此不同。我会假设 O(n) 因为它有一个迭代循环。

这是一篇带有漂亮图表的中等文章。

function factorial (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  }
  let prev = 1;
  let ret;
  while(n >= 2) {
    ret = prev * n;
    prev = ret;
    n--;
  }
  return ret;
}

function factorialR (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  } else {
    return n * factorialR(n - 1);
  }
}

递归版本似乎需要更长的时间。请参阅此处的 SO Q/A。.

标签： javascriptbig-o

解决方案

是的，这些函数都具有O(n)计算复杂性，其中 n 是传递给初始函数调用的数字。

第一个函数在循环中为较大和 2 之间的每个值执行 ( O(1)complexity) 语句，总体复杂度为.whilenO(n)

第二个函数递归调用自身n时间，没有任何循环，（再次）整体复杂度为O(n).

如果您想降低函数多次调用的计算复杂度，我会创建一个查找表来保存从先前调用计算的值，从而导致m函数调用运行O(n)（其中n是有史以来传递的最高数字），​​而不是比在（或）时间内m运行的调用。O(n * m)O(n^2)

如果

递归版本似乎需要更长的时间。

这不是由于计算复杂性，而是由于编译器如何使用不同的方法。函数调用通常比简单的while循环有更多的开销（虽然，这种优化在现实生活中几乎从不担心 - 代码的可读性和可维护性在大多数情况下更为重要）。

推荐阅读