初學紀錄 - Linear Search

紀錄過程

Linear Search → 號稱最簡單的演算法

Pseudocode

(P 不發音)

不是真正的程式碼，只是用來表達情境

parameter 參數

思考一下我還記得 For loop 跟 While loop 差別嗎？

想像中是表示從第一個開始尋找，找到最後一個，找到就回傳，如果真的沒找到全部跑完，那就回傳 -1。

作用在 Array 的時候。

那所謂最糟糕的情況就是就是要全部跑完都找不到，會在 Array 的最後一項。

如果總共有 n 項(index)，就會從頭 0、1 找到 n-1，每個都找一次就像是

for i → i → … → i

所以最壞狀況 Worst Case Performance： O(n)

最好的情況就是馬上找到，就直接在第一項。

Best Case Performance： O(1)

所以平均下來，你要找到你要的 n 的話

Average performance： O(n/2)

做個整理，

我覺得這個相對單純簡單，所以沒有太大問題，

目前有一些疑惑是：

指的是演算法額外需要多少記憶體空間，這並不包括輸入本身。

Linear Search 的話如果程式是這樣寫：

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

可以發現空間使用上只有一個 i 的技術變數，所以今天不管這個 arr 是 10 個元素，或是 1000 個元素，使用到了變數數量都一樣，不會隨輸入變大而要更大空間。

所以空間複雜度是 O(1)。

沒有排序的情況下，只能一個個找。

例如一個亂序的購物清單 ["牛奶", "蛋", "咖啡"]，要找「咖啡」就只能一個一個比對。

因為它很簡單，所以如果一個陣列只有幾十個元素的時後，用 linear search 其實又快又方便

因為 linear search 雖然比較慢，但他的空間複雜度只有 O(1)，代表不會隨著輸入變大而額外吃掉記憶體。

在記憶體有限的情況下實用。

Linear Search