用JavaScript學習資料結構與演算法 1：演算法與大 O 符號

Long

10 min readSep 14, 2019

演算法

在進入到大 O 符號之前，我們先來介紹一下甚麼是演算法(algorithm)。估狗之後，可以從維基百科中獲得演算法的介紹:

演算法（algorithm），在數學（算學）和電腦科學之中，為任何良定義的具體計算步驟的一個序列，常用於計算、資料處理和自動推理。精確而言，演算法是一個表示爲有限長列表的有效方法。演算法應包含清晰定義的指令用於計算函式。

恩，說實話，其實還蠻難理解的（良定義感覺是個很善良的定義呢囧）；後來在網路上有找到我認為比較好理解的說明：

演算法由三個部分組成：輸入、計算步驟、輸出；它是明確的、有限的、且有效率的。

舉例來說，假設我今天想要砍倒一顆很大的樹，那碰到的問題就是：如何將這顆樹砍倒？我們可以選擇跟樵夫借把斧頭，然後捲起袖子，一刀一刀的砍，最後將樹給砍倒。用演算法的來解釋的話，輸入即是斧頭，計算步驟為我們劈砍的過程，輸出即是樹倒下了。

我們有沒有甚麼其他的方法來達成目的呢？當然有的！想像一下，今天我們將樵夫的斧頭換成電鋸，啟動開關後直接使用，一樣可以將樹砍倒。相信大家應該會覺得使用電鋸會是個比較好的做法，既節省了時間，也省去了不少力氣。

那麼，在程式設計中，我們是如何評估一個演算法的好壞呢？是程式的執行速度嗎？還是執行時所占用的記憶體空間？亦或是程式的可讀性呢？這些其實都要考慮進去，而在考量執行的速度與記憶體空間時，我們用複雜度來描述一個演算法的趨勢，這個趨勢就是使用大 O 符號來進行描述。

大 O 符號

大 O 符號，又稱為漸進符號，是一種描述函數輸入對應函數增長之間關係的方式；在大 O 符號中，我們只關注其「趨勢」，並不會留意其他的細節。這是甚麼意思呢？讓我舉個生活中的例子來說明吧！我有個朋友叫阿敏，他的興趣是收藏鞋子，只要是他看上鞋子，不論價格多少他都買的下去。這天他又買了一雙鞋，價格為一萬三千五百元，到家後媽媽問他這雙新鞋花了多少錢呢？阿敏回答：沒多少錢耶，大概「一萬多」塊吧！這邊的「一萬多」就有大 O 精神在裡面了，因為在整體的價格中，千元與百元的影響相較於萬元來說小了很多，所以這邊會以萬元代表整體的「趨勢」。

所有範例程式碼: 程式

那在程式中要怎麼使用大 O 符號呢？讓我們看看以下的例子：

function shoes(n) {
  let value = n+1;
  return value
}

這個函數執行的步驟次數為 2，即使輸入的 n 趨近於無窮大，仍是只會執行兩次。因此在大 O 符號中我們會標注成 O(1)，說明他是個固定的常數，與輸入沒有任何關係。再看下面這個例子：

function shoes(n) {
  let value = n+1;
  for (let index = 0; index < value; index++) {
    console.log("阿敏有"+ index + "雙鞋子");
  }
  return value
}
shoes(8)

與上面例子不一樣的是，這個函式中多了一個迴圈，且這個迴圈會受輸入的 n 影響，n 越大，執行的步驟次數就越多。因此這個函式整體的步驟次數為： n+2；但我們剛才說了，大 O 符號只關注整體的趨勢，並不會在意細節，因此這邊會將其標注為 O(n)，說明執行的步驟次數是會隨著輸入 n 線性成長的。

好了，相信經過剛才的例子，大家應該對於大 O 符號多少也些認識了吧！接著我們回到一開始的問題：如何評估一個演算法的好壞呢？對於這個問題，我們需要從時間（程式執行時的步驟次數）與空間（程式執行時所佔用的記憶體空間）來做分析，以下將介紹時間複雜度及空間複雜度。

時間複雜度

時間複雜度，簡單來說就是電腦執行一個演算法所需要花費的時間成本，但這邊的時間成本不是說實際電腦在執行時所花的時間，因為每台電腦的效能不同，可能你的電腦好一點跑這個演算法只需要10秒鐘，我的電腦卻需要30秒才能跑完；為了能在「相同的基準下」判斷其花費的時間成本，我們使用程式執行時需要的步驟次數來進行衡量。講到這邊相信大家也發現了，我們剛剛的例子就是在計算步驟次數，得到的結果 O(1)、O(n) 其實就是時間複雜度。讓我們再來看一個更進階的例子:

function shoes(n) {
  let value = n+1;
  for (let index = 1; index < value; index++) {
    console.log("阿敏買了"+ index + "雙鞋子");
    for (let j = 1; j < value; j++) {
      console.log("阿敏買了"+ j + "雙襪子");
    }
  }
  return value
}
shoes(8)

從程式中可以得知，我們的阿敏每買一雙鞋，就會再買 n 雙襪子。整體的執行步驟次數為 n² + 2。考量整體的趨勢，故其大 O 符號為 O(n²)，我們可說這個演算法的時間複雜度為 O(n²)。

步驟次數對應輸入個數的關係可參考下面這張圖(引用自胡程維的這篇文章)，從這邊我們可以知道，在進行較為複雜的運算時，時間複雜度較佳的演算法確實能節省不少的時間。

空間複雜度

空間複雜度是指執行程式時所需要記憶體量。考量下面這個例子：

function show(n) {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
}

從這個例子我們可以快速的看出其時間複雜度為 O(n)，那空間複雜度呢？不管程式的執行步驟數是多少，我們的變數數量始終只有 i，因此空間複雜度為O(1)。再考量下面這個例子：

function show(n) {
  let array = [];
  for (let i = 0; i < n; i++) {
    array.push(i);
  }
  console.log(array);
}
show(5)

由於 array 的 push 方法會讓記憶體的佔用量隨著輸入的 n 增加而線性成長，故這個演算法的空間複雜度為 O(n)。

現在，我們已經知道甚麼是時間複雜度與空間複雜度了，而在評估一個演算法的效能時，這兩者都需要考慮到，通常一個時間複雜度較佳的演算法，空間複雜度就會有一定程度的犧牲，反之亦然；因此需要根據自身的需求，選擇合適的演算法，下面將會用一個案例來討論時間/空間複雜度較佳的做法。

案例：輸入兩個陣列，檢查第一個陣列的元素是否有出現在第二個陣列中，且出現頻率一致。

先來看看第一個解法：

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {//長度需要一致
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    const element = arr1[i];
    const index = arr2.indexOf(element);//第二個迴圈
    
    if (index === -1) {//元素沒有出現在arr2
      return false
    }else{
      arr2.splice(index,1)//有的話就從arr2中將元素移除
    }
  }
  return true
}
console.log(same([1,2,3,1],[3,1,2,1]));//true

輸入兩個陣列後，首先會檢查兩個陣列的長度是否一致，確認一致後會對第一個陣列的每個元素做迭代，檢查當前的元素是否有出現在第二個陣列中，有的話就將元素從第二個陣列中移除，沒有的話則返回 false ，最後若都有找到的話，會回傳 true。

接著來分析下這個演算法，首先可以看到在函式中有個迴圈對第一個陣列做迭代，並且在內部為了檢查當前的元素是否有出現在第二個陣列中，使用了 indexOf 的語法對陣列二再進行了一次迭代，因此這個演算法的時間複雜度為 O(n²)。而輸入的兩陣列不論有多少元素，皆不會佔用影響記憶體空間，因此其空間複雜度為 O(1)。

再來讓我們看看這個解法：

function same1(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }
  const freqCount1 = {};
  const freqCount2 = {};
  for (item in arr1) {
    freqCount1[arr1[item]] = ( freqCount1[arr1[item]] || 0)+1 ;
  }
  for (item in arr2) {
    freqCount2[arr2[item]] = ( freqCount2[arr2[item]] || 0)+1 ;
  }
  
  for (item in freqCount1) {
    if(!freqCount2.hasOwnProperty(item)){//判斷第二物件是否有這個key
      return false
    }
    if (freqCount1[item] !== freqCount2[item]) {//檢查兩邊key值
      return false
    }
  }
  return true
}
console.log(same1([1,2,3,1],[3,1,2,1]));//true

一樣是先檢查兩組長度是否一致，接著宣告兩個物件，用來存放不重複的元素及其出現的頻率，接著對第一個陣列與第二個陣列個別進行一次迴圈，將不重複的元素當做 key 存入物件，value 則存入其出現的頻率。接著我們對物件 freqCount1 做遍歷，並用 hasOwnProperty 這個方法判斷兩邊是否有相同的 key，若有的話再檢查是否有相同的 value，皆符合的話最後會回傳 true。分析這個演算法，在其中會看到三組迴圈，需要注意的是第三個迴圈中的 hasOwnProperty 方法是直接對物件的 key 進行查找(時間複雜度為 O(1))，故這個演算法的時間複雜度為 O(n)。空間複雜度的部分，隨著陣列的元素值增加(考慮最差情況，即輸入元素皆不重複)，其所佔用的記憶體空間也會線性增加，故其空間複雜度為 O(n)。

整理一下結果兩組答案的結果：