首頁 >web前端 >js教程 >如何用 JavaScript 寫簡單的 Memoization 函數程式碼？

如何用 JavaScript 寫簡單的 Memoization 函數程式碼？

PHPz轉載: 2023-08-25 08:17:02871瀏覽

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

記憶化是提高函數效能的最佳化技術。在我們開始記憶技術之前，讓我們使用下面的範例來了解為什麼我們需要它。

範例（尋找斐波那契數的簡單方法）

在下面的範例中，我們實作了簡單的方法來找出第 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⁴ 的輸入值時，它需要比平常更多的時間，並且對於範圍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>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>

在本教程中，我們學習了優化程式碼的記憶技術，使其更加節省時間和空間。使用者可以在第二個和第三個範例中使用不同的演算法看到我們如何最佳化第一個範例的程式碼。

以上是如何用 JavaScript 寫簡單的 Memoization 函數程式碼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述：

本文轉載於：tutorialspoint.com。如有侵權，請聯絡admin@php.cn刪除

上一篇：Node.js 中的 decipher.update() 方法下一篇：Node.js 中的 decipher.update() 方法

看更多