資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
