iT邦幫忙

2022 iThome 鐵人賽

DAY 3
0
Software Development

刷題也算一種電競吧:演算法與資料結構系列 第 3

Day 2 哎呀這什麼水平 - 時間與空間複雜度

  • 分享至 

  • xImage
  •  

Day 1 我們講到的複雜度表示都是指時間複雜度,在輸入的參數越多越大的情況下,所要執行的步驟(執行所需花費的時間)的增長趨勢。

我們也可以使用 Big O notation 来表示空間複雜度。

空間複雜度指的是在輸入的參數越多越大的情況下,執行該演算法所需要記憶體空間的增長趨勢。

空間複雜度考慮的是執行演算法時所需要的記憶體,不考慮輸入的參數的大小。

Space Complexity in JS

  • 原始型別的資料: 如數字、布林值、nullundefined 等等,空間複雜度是 O(1) (constant space)。
  • 字串: 空間複雜度是 O(n) (linear space)。字串越長,所需的空間越多。
  • 物件與陣列: 空間複雜度是 O(n)。 物件的鍵值越多 (key),陣列的長度越長,所需的空間越多。

Examples

function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

我們來看上面的函式,宣告 total 變數存數字,在迴圈中反覆加總,最後回傳 total

就算 arr 參數本身長度無限大,影響的只有時間複雜度。函式裡面只有用到 totali 這兩個數字變數,所以此算法的空間複雜度是 O(1)

function double(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i] * 2);
  }
  return newArr;
}

把輸入的陣列內元素全部乘以 2,最後回傳一個新的陣列。

在這個函式,輸入的陣列越長,newArr 也會越長,所需的空間當然也越多,所以空間複雜度是 O(n)

Recap

  1. 我們使用 Big O notation 來表示一個演算法的效能。
  2. Big O notation 能用來表示時間或空間複雜度。
  3. Big O notation 只看複雜度的增長趨勢 (linear, quadratic, constant),而不是精確的計算。
  4. 時間或空間複雜度不考慮執行演算法的硬體如何,只考慮演算法本身。

上一篇
Day 1 這到底是什麼符號喔齁齁齁齁齁 - Big O Notation
下一篇
Day 3 好用兩件套 - 物件與陣列的時間與空間複雜度
系列文
刷題也算一種電競吧:演算法與資料結構34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言