為什麼要了解？

在我還是個剛轉職成功，沒有實際接觸過複雜專案的菜雞時期，面對新功能的開發，心態上保持著 先求有再求好，寫出許許多多用了不同內建函式、自訂函式的程式碼。新功能當然是順利開發成功，為此感到十分開心。這時候的我，對於能完成新功能開發的自己，感到十分得意。

工作經驗增加後，有機會碰到公司內較複雜的專案，藉此打開我的眼界，程式碼的部分沒有毫無章法的寫法，反倒是有一定規律的做法（現在的我知道這是 Design Pattern），當時我負責接觸的部分是效能優化的部分，這時候才感覺到沒有思考每種資料結構特性，胡亂使用順眼的函式執行，是一件多麽可怕的事情。

回憶結束。

關於程式碼的效率，可以從兩個角度來思考：

• 執行速度可以多快？
• 執行時期記憶體使用量有多少？

菜雞時期接觸的專案，鮮少有大數量（萬筆以上）的資料庫，或是每天接受的 Request 數量到達幾十萬甚至是幾百萬。因此在處理資料上都是小數量為主，任何的函式在執行上看不太出來效率的差異。但是，真實世界，尤其是開發逐漸上軌道的產品，不可能面對小數量，而是讓人無法有人平估的大數量。是否善用資料結構與演算法來優化產品的邏輯運算，在這個時候就派上用場了。當然，除了優化處理效率外，還有許多跟部署有關的技術可以優化大數量的 Request，這不在本文討論的範圍內。

回到主題，判斷執行速度與記憶體的使用，可以這樣理解：

時間複雜度，Time Complexity

強調需要執行的次數。

專業上的講法會提到測量方式、測試次數的加總以及如何用 Big O 表達，個人傾向簡單講解，面對一組資料，用 for-loop 執行嗎？假如面對多組資料，能避開巢狀 for-loop 嗎？有想過在 for-loop 調整執行的內容，好減少執行的次數。

空間複雜度，Space Complexity

強調變數的使用量。

專業上的講法會提到執行時要佔用的記憶體空間，個人傾向簡單講解，面對一組資料，是否要額外宣告變數來處理？變數的數量可以控制嗎？

two sum 這題該怎麼看待

暴力解

const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) { // 第一個迴圈
    for (let j = i + 1; j < nums.length; j++) { // 第二個迴圈
      if (nums[j] = target - nums[i]) {
        return [i, j];
      }
    }
  }

  return [];
}

時間複雜度的部分，第一個迴圈，陣列內每一個項目都要被執行一遍，所以執行次數是 nums.length，在分析時習慣用 N 表達。針對陣列內每一個項目，會需要第二個迴圈，執行次數是 nums.length - 1，分析用 N-1 表達。

因此這題的時間複雜度是：

O(N * (N-1))
-> O(N^2 - N) // 相乘
-> O(N^2) // 只保留最大的數字

空間複雜度方面，沒有額外宣告任何變數。

因此，暴力解在執行時間方面會是 O(N^2)，記憶體方面幾乎沒有大負擔。

使用 Hash Table

const twoSum = (nums, target) => {
    const comp = {}; // 額外宣告的變數

    for (let i=0; i<nums.length; i++){ // 第一個迴圈
        if (comp[ nums[i] ] >= 0 ) {
            return [ comp[nums[i] ], i]
        }

        comp[target-nums[i]] = i
    }
};

時間複雜度的部分，僅僅只有一個迴圈，執行次數是 nums.length。

因此這題的時間複雜度是：O(N)。

空間複雜度方面，額外宣告 Hash Table，隨著 N 的數量增長，Hash Table 內的資料量將跟著成長。

因此，Hash Table 在執行時間方面會是 O(N)，記憶體方面則有負擔。

題外話

這題嘗試用不同語言撰寫，有趣的地方在於，我直覺認為靜態語言就是比動態語言快速，殊不知 C# 賞我一巴掌，而記憶體的使用方面，Java 與 C# 也賞我兩巴賞。這邊有幾點可以推論：

• 這題的寫法，在記憶體的存取方面，對於 Java 與 C# 有比較大的負擔。
• LeetCode 官方的模擬環境，與我認知的不太一樣。
• Golang 出人意料的快速，怪不得 Google 自誇是 21 世紀的 C 語言。

就我個人經驗而言，撰寫 JS 與 Java 的時候幾乎沒在管記憶體，追求的只有更高的效率。直到接觸用 C 開發的機器，被 free 給嚇到，給我一個機會省思過度宣告變數的好壞。

結語

任何專業領域都一定有測不準原理的窘境，在程式設計的便是記憶體與時間的抉擇。拜摩爾定律協助半導體產業的發展，記憶體朝向大儲存量與低廉價格發展，使得空間複雜度變成次要，時間複雜度成為主要關注的重點。最典型的運用便是各式各樣的網頁，使用者不能忍受3秒以上的等待，於是瀏覽器們著重在使用記憶體，好帶給使用者快速的體驗。

那有著重空間複雜度的場合嗎？有的，在部分伺服器、嵌入式系統等，提供的是有限的記憶體，此時該思考如何在有限的記憶體下，爭取到多少時間？

當然，目前各大公司提到演算法時，仍舊著重在時間複雜度，記憶體的問題在特定產業才有可能遇到，因此，寫出能夠快速執行的程式碼幾乎是各大公司要求的基本功。