如何用 JavaScript 编写简单的 Memoization 函数代码？-js教程-PHP中文网

首页

web前端

js教程

如何用 JavaScript 编写简单的 Memoization 函数代码？

PHPz

Aug 25, 2023 am 08:17 AM

如何用 JavaScript 编写简单的 Memoization 函数代码？

记忆化是提高函数性能的优化技术。在我们开始记忆技术之前，让我们使用下面的示例来了解为什么我们需要它。

示例（查找斐波那契数的简单方法）

在下面的示例中，我们实现了简单的方法来查找第 n 个斐波那契数。我们使用递归方法来找到第 n 个斐波那契数列。

<html>
<body>
   <h3 id="Finding-the-nth-Fibonacci-using-recursive-approach-number-in-JavaScript">Finding the nth Fibonacci using recursive approach number in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number.</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "executeFunc()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      
      // function to write the fibonacci series
      function findFib(n) {
         if (n <= 1) return n;
         return findFib(n - 1) + findFib(n - 2);
      }
      function executeFunc() {
         let n = document.getElementById('fib').value;
         content.innerHTML = "The " + n + "th fibonacci number is " + findFib(n);
      } 
   </script>
</body>
</html>

上面的例子对于小于 1000 的小输入值来说效果很好，但是当我们输入范围 10⁴ 的输入值时，它需要比平常更多的时间，并且对于范围 10 的输入⁶，由于内存越界导致浏览器崩溃。

我们可以使用记忆技术来优化上面的代码，它允许我们存储之前计算的结果。例如，要找到第 4 个斐波那契数，我们需要找到第 3 个和第 2 个斐波那契数。同样，要找到第三个斐波那契数，我们必须找到第二个和第一个斐波那契数。因此，这里我们计算了第二个斐波那契数两次。

现在，假设您想要找到第 n 个大值的斐波那契数列，您可以想想它需要多少次重复。因此，出于优化目的，我们可以第一次计算第二个斐波那契数并将其存储在临时变量中。之后，当我们需要再次计算第二个斐波那契数时，我们可以从数组中访问它，从而使代码更加高效。

此外，将先前计算的结果存储在数组中以供以后使用也是记忆化。

语法

用户可以按照下面的语法来实现记忆第n个斐波那契数。

if (temp[n]) return temp[n];
if (n <= 1) return n;
return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);

在上面的语法中，我们首先检查‘temp’对象中是否已经存在第n个斐波那契数，然后返回该值；否则，我们计算它的值并将矿石添加到临时对象中。

方法

步骤 1 – 使用 if 语句检查临时对象中是否存在 n 的结果。如果是，则返回之前计算的值。

步骤 2 – 如果 n 小于或等于 1，则返回 1 作为递归函数的基本情况。

第 3 步 – 计算 n-1 和 n-2 斐波那契数，将它们相加并将它们存储在临时对象中以供以后使用。

第 4 步 – 将第 n 个斐波那契数存储后返回到临时对象。

示例（使用记忆查找第 n 个斐波那契数）

使用记忆技术，我们优化了下面示例中第一个示例的代码。我们使用 temp 对象来存储之前计算的结果。在输出中，用户可以观察到下面的代码比第一个示例的代码更高效。

<html>
<body>
   <h3 id="Finding-the-nth-Fibonacci-number-using-memoization-using-extra-space-in-JavaScript">Finding the nth Fibonacci number using memoization using extra space in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number.</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "start()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      function findFib(n, temp) {
         if (temp[n]) return temp[n];
         if (n <= 1) return n;
         return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);
      } 
      function start() {
         let n = document.getElementById('fib').value;
         content.innerHTML = "The " + n + "th fibonacci number using memoization is " + findFib(n, {}) + "<br>";
      }
   </script>
</body>
</html>

方法：使用记忆而不使用额外空间

第 1 步 – 将 a 初始化为 0，将 b 初始化为 1。

第 2 步 – 使用 for 循环进行 n 次迭代来查找第 n 个斐波那契数。

第 3 步 – 这里，c 是一个临时变量，存储第 (i-1) 个斐波那契数。

第 4 步 – 将 b 变量的值存储在 a 中。

第 5 步 – 将变量 c 的值存储在变量 b 中。

示例

下面的示例也是第一个示例的优化变体。在第二个示例中，我们使用 temp 对象来存储先前计算的结果，但在下面的代码中，我们使用名为 c 的单个临时变量。

下面的代码是查找斐波那契数列的最有效方法，因为其时间复杂度为 O(n)，空间复杂度为 O(1)。

<html>
<body>
   <h3 id="Finding-the-nth-Fibonacci-number-using-memoization-in-JavaScript">Finding the nth Fibonacci number using memoization in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number:</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "findFib()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      
      // function to write the fibonacci series
      function findFib() {
         let n = document.getElementById('fib').value;
         let a = 0, b = 1, c;
         if (n == 0) {
            return a;
         }
         for (let i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
         }
         content.innerHTML += "The " + n + "th Fibonacci number using memoization is " + b;
      }
   </script>
</body>
</html>

在本教程中，我们学习了优化代码的记忆技术，使其更加节省时间和空间。用户可以在第二个和第三个示例中使用不同的算法看到我们如何优化第一个示例的代码。

以上是如何用 JavaScript 编写简单的 Memoization 函数代码？的详细内容。更多信息请关注PHP中文网其他相关文章！

声明

本文转载于：tutorialspoint。如有侵权，请联系admin@php.cn删除

C和JavaScript：连接解释Apr 23, 2025 am 12:07 AM

C 和JavaScript通过WebAssembly实现互操作性。1）C 代码编译成WebAssembly模块，引入到JavaScript环境中，增强计算能力。2）在游戏开发中，C 处理物理引擎和图形渲染，JavaScript负责游戏逻辑和用户界面。

从网站到应用程序：JavaScript的不同应用Apr 22, 2025 am 12:02 AM

JavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中，JavaScript与HTML、CSS一起操作DOM，实现动态效果，并支持如jQuery、React等框架。2)通过ReactNative和Ionic，JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行，支持高并发请求。

Python vs. JavaScript：比较用例和应用程序Apr 21, 2025 am 12:01 AM

Python更适合数据科学和自动化，JavaScript更适合前端和全栈开发。1.Python在数据科学和机器学习中表现出色，使用NumPy、Pandas等库进行数据处理和建模。2.Python在自动化和脚本编写方面简洁高效。3.JavaScript在前端开发中不可或缺，用于构建动态网页和单页面应用。4.JavaScript通过Node.js在后端开发中发挥作用，支持全栈开发。