在開始用JavaScript實作各種資料結構前，總要先了解什麼是資料結構吧，才會知道之後學習的鏈結串列/堆疊/佇列是什麼東西啊~那廢話不多說，我們就開始吧!

資料結構是什麼?

我們就從資料開始說起吧，在我們寫程式時，經常不可避免會將資料進行處理(例如新增/刪除/搜尋等等)，那麼當資料變的龐大時，要怎麼有效率的整理這些資料呢?肯定是必須透過一些特殊的方法去將資料做組織化的的管理，因此將資料進行整理，有利於電腦將資料做儲存處理的這些方式就叫資料結構。

那演算法又是什麼?

簡單的說它就是用於解決一個問題的一連串步驟，而它必須滿足幾項特性，這裡將用一個尋找[1, 5, 2]陣列中最大值的問題為例:

1. 輸入: 需要有一個或數個輸入的值(這邊的輸入值是[1, 5, 2])

2. 輸出: 為輸入值經過演算法計算後產出的值(想當然最大值是5)

3. 明確性: 意思是每一個運算的步驟必須明確

比如此找最大值的問題步驟是:

1. 先預設1為最大值
2. 移到陣列資料值5的位置，發現5比1大，設5為最大值
3. 移到陣列資料值2的位置，發現5比2大，5還是最大值
4. 輸出結果為5是最大值

每個步驟都相當明確，而且符合找出最大值問題的需求

4. 有限性: 在有限步驟後一定會結束，也就是不會一直執行下去(找出最大值後程式就結束了)

5. 有效性: 步驟清楚可行，能確實用數學運算出該步驟結果

在介紹演算法之後，要來介紹與它相關的兩個名詞和大O符號(Big O Notation):

大O符號(Big O Notation)

它是常用來衡量一段程式碼的演算法複雜性、執行時間(記憶體)的一個符號，在最壞的執行案例中，執行時間不會超過Big-Ο。

那為什麼要使用這個符號去代表演算法的執行時間，而不是直接用毫秒等數字代表，那是因為每次程式執行的時間都不太一樣，且不同機器跑時間也不一樣，故使用這個函數去統一衡量演算法的執行時間。

空間複雜度(Space Complexity)

指演算法所需要消耗的儲存記憶體資源

1. 大多數原始型別(布林、數字、undefined、null)都為 O(1)
2. 字串為 O(n)
3. 物件型別如陣列、物件為 O(n)，根據他們的元素數量、key 數量線性成長...

範例1:

此範例空間複雜度為 O(1)，total 和 i 都是數字

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

範例2:

因為 newArr 的關係，此範例空間複雜度為 O(n)

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

時間複雜度（Time complexity）

用於評估該演算法執行的時間快慢

這兩個常用的複雜度都可以用大O符號表示，以下介紹了幾個常見的時間複雜度:

Constant Run Time O(1): 常數

這個演算法（函式）的執行時間不會隨著輸入資料量的增加而增加。

let i = 1;
let j = 4;
i = i * j;

分析: 在i = i * j時，i取值為1，j取值為4，只經過一次查找就取得數值故時間複雜度為O(1)
i 和 j 所分配的空間都不隨著處理資料量變化，因此它的空間複雜度為O(1)

Linear Run Time O(n): 線性

當我們輸入的資料越多的時候，它就會需要等比例地輸出越多的內容給我們，因此會需要消耗等比例多的時間

let i = 1;
while( i < n) {
    i++;
}

分析: 由於i在>=n之前，運行了n次while迴圈，故時間複雜度為O(n)

注意: 不是所有的迴圈都是 O(n)，下面的範例就是 O(1)

function logAtMostTo5(n) {
  for(let i = 0; i < Math.min(5, n); i++) {
    console.log(i);
  }
}

Exponential Run Time O(n^2): 平方

隨著資料量的增加，執行時間會以指數成長

for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
    
    }
}

分析: 運行了兩層迴圈，也就是n*n次，故時間複雜度為O(n^2)

Logarithmic Run Time O(log n): 對數

隨著資料量增加，執行時間雖然會增加，但增加率會趨緩。
常見範例: 二元搜尋(將一個由小到大排序的陣列透過不斷減半的方式找到目標的演算法)

補充-物件 & 陣列的時間複雜度

物件

只有搜尋是 0(n)，其他像是新增、移除和取得屬性都是 0(1)

陣列

• 取得: 0(1)
• 搜尋: 0(n)
• 插入: 不一定，在陣列最後面加上元素則為 0(1)，在陣列開頭插入則為 0(n)
• 移除: 不一定，在陣列最後面移除元素則為 0(1)，在陣列開頭移除則為 0(n)

Static Array: 固定長度並且陣列內每個值都有索引
Dynamic Array: 可動態的新增刪除陣列元素

其他和陣列有關的函式如 concat()、slice()、splice() 都是 0(n)，Array.sort() 比較特別，是 O(n * log n)，在 V8 引擎中，是透過 Timsort 演算法實作的，讀者也可以參考看看 V8 blog 的文章:

https://v8.dev/blog/array-sort

補充-抽象資料型態（Abstract Data Type，ADT）

是一種只定義數學觀念，將資料和操作一起思考的觀念。這種資料型態著重於資料的運算操作，並不考慮實作時的細節或資料本身的性質
Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector are ADTs. Each of these ADTs has many implementations

以上就是資料結構和演算法的基礎介紹!明天，我們將來了解陣列囉~