极客笔记如何在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的输入值正常工作，但是当我们输入范围为10的4次方时，会比平常花费更长的时间，而对于范围为10的6次方的输入，由于内存超出范围，会导致浏览器崩溃。
我们可以使用记忆化技术来优化上述代码，这让我们可以存储先前计算出的结果。例如，要找到第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对象中。
方法
第一步 - 使用if语句检查temp对象中是否存在n的结果。如果是，则返回先前计算的值。
第二步 - 如果n小于或等于1，则将1作为递归函数的基本情况返回。
第三步 - 计算n-1和n-2的斐波那契数，并将它们相加并存储在temp对象中以供以后使用。
第四步 - 在存储之后，将第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>
在本教程中，我们学习了记忆技术以优化代码，使其在时间和空间上更有效率。用户可以看到我们如何使用不同的算法对第一个示例的代码进行优化，转化成了第二个和第三个示例。