JavaScript动态规划与递归性能对比：以斐波那契数列为例

动态规划与递归的性能对比

本文通过具体实例解析JavaScript中的高级算法——动态规划，旨在为读者提供可参考的学习资料。

这一内容源于对《数据结构与算法》一书的研读与思考。尽管该书在学术界存在一定争议，被指存在若干漏洞，但这并不影响其作为知识载体的价值，我们仍可从中汲取有益的技术观点。

在前端开发实践中，高级算法的应用场景相对有限。大多数常规逻辑可以通过if、for、switch等基础控制语句解决；面对稍复杂的逻辑时，开发者通常会优先考虑使用递归方案。

然而需要警惕的是，虽然递归写法往往简洁直观，但其实际运行效率通常并不理想。

接下来，我们将探讨动态规划算法的具体应用。

动态规划的核心思想是自底向上地解决问题：先解决所有子问题，再将子问题的解合并，从而构建出整个大问题的最终解决方案。

斐波那契数列实例分析

为了直观展示这一过程，我们以计算斐波那契数列为例进行说明。

斐波那契数列是一个经典的数学序列，其前几项为：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368……

该数列的定义规则从第3项开始，即每一项数值均等于其前两项数值之和。

针对这一数列特性，我们可以编写一个递归函数来计算第n项的数值。

// 斐波那契数列
function recurFib(n) {
    if(n < 2){
      return n ;
    }else {
//          document.write("第"+(n-1)+"次计算&nbsp;n-1="+(n-1)+recurFib(n-1)+'&nbsp;&nbsp;&nbsp;');
//          document.write("n-2="+(n-2)+recurFib(n-2)+"<br>");
      return recurFib(n-1)+recurFib(n-2)
    }
}

上述递归代码确实非常简洁。代码中注释部分曾用于打印当n为特定值时函数的执行次数，通过观察可以发现，随着n值的增加，函数调用的次数呈爆炸式增长，这在直观上揭示了递归效率低下的问题。

当n=5时，递归调用树已经相当庞大；可以预见，当n达到10甚至100时，计算开销将变得极其巨大。

动态规划优化方案

在理解递归函数效率低下的原因后，我们来看看动态规划是如何优化这一过程的。

function dynFib(n) {
  let val = [];
  for(let i = 0; i <= n; ++i){
    val[i]=0;
  }
  if(n ===1 || n === 2){
    return 1;
  }
  else {
    val[1] =1;
    val[2] = 2;
    for(let i = 3; i <= n; ++i){
      val[i] = val [i-1] +val[i-2] ;
    }
  }
  return val[n-1]
}

动态规划方案利用数组val来存储中间计算结果。如果输入的斐波那契数n为1或2，if语句直接返回1；否则，数值1和2将被分别存储在数组val的索引1和2的位置中。

随后，循环从3遍历至输入参数n，将数组每个元素的值赋为其前两个元素之和。循环结束后，数组最后一个元素的值即为最终计算得到的斐波那契数值，该值也将作为函数的返回值。

性能测试与迭代优化

为了量化对比两种算法的性能差异，我们可以编写一个简单的测试函数来测量它们的运行时间。

// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write('<br>'+'当n='+n+'的时候&nbsp;'+res+'<br>');
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

以下是用于打印函数执行时间的测试代码。

let time = test(recurFib,40);
document.write(time);
let time2 = test(dynFib,40);
document.write(time2);

运行结果如下所示：

最后，你可能已经注意到，在使用迭代方案计算斐波那契数列时，实际上是可以不使用数组的。

之所以在之前的动态规划示例中使用数组，是因为该算法通常需要将中间计算结果保存起来以便复用。

以下是优化后的迭代版本斐波那契函数定义。

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i < n; ++i) {
    result = last + nextLast;
    nextLast = last;
    last = result;
  }
  return result;
}

当然，这个纯迭代版本的实现与之前使用数组的动态规划版本在效率上是相同的。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述的算法对比与分析能对JavaScript程序设计有所帮助。