数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何在 JavaScript 中编写简单的记忆化函数代码？
记忆化是一种优化技术，用于提高函数的性能。在开始记忆化技术之前，让我们通过下面的示例了解为什么我们需要它。
示例（查找斐波那契数的朴素方法）
在下面的示例中，我们实现了查找第 n 个斐波那契数的朴素方法。我们使用递归方法来查找第 n 个斐波那契数列。
<html>
<body>
<h3>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 的小输入值可以正常工作，但是当我们输入 104 范围的输入值时，它花费的时间比平时更长，并且对于 106 范围的输入，由于内存超出范围而导致浏览器崩溃。
我们可以使用记忆化技术来优化上述代码，这使我们能够存储先前计算的结果。例如，要查找第 4 个斐波那契数，我们需要查找第 3 个和第 2 个斐波那契数。同样，要查找第 3 个斐波那契数，我们必须查找第 2 个和第 1 个斐波那契数。因此，在这里我们计算了两次第 2 个斐波那契数。
现在，假设您想为较大的第 n 个值查找斐波那契数，并且您可以想到它需要多少重复。因此，为了优化，我们可以第一次计算第 2 个斐波那契数并将其存储在临时变量中。之后，当我们再次需要计算第 2 个斐波那契数时，我们可以从数组中访问它，从而使代码更高效。
此外，将先前计算的结果存储在数组中以供以后使用就是记忆化。
语法
用户可以遵循以下语法来实现记忆化以查找第 n 个斐波那契数。
if (temp[n]) return temp[n]; if (n <= 1) return n; return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);
在上面的语法中，我们首先检查第 n 个斐波那契数是否已存在于“temp”对象中，然后我们返回该值；否则，我们计算其值并将其存储到 temp 对象中。
方法
步骤 1 – 使用 if 语句检查 temp 对象中是否存在 n 的结果。如果是，则返回先前计算的值。
步骤 2 – 如果 n 小于或等于 1，则返回 1 作为递归函数的基本情况。
步骤 3 – 计算 n-1 和 n-2 斐波那契数，将它们加起来并存储在 temp 对象中以供以后使用。
步骤 4 – 将第 n 个斐波那契数存储到 temp 对象后返回。
示例（使用记忆化查找第 n 个斐波那契数）
使用记忆化技术，我们在下面的示例中优化了第一个示例的代码。我们使用了 temp 对象来存储先前计算的结果。在输出中，用户可以观察到以下代码比第一个示例的代码更有效。
<html>
<body>
<h3>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>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>
在本教程中，我们学习了记忆化技术来优化代码，使其在时间和空间上更高效。用户可以看到我们在第二个和第三个示例中如何使用不同的算法优化第一个示例的代码。
311 次浏览
