上一講我們聊到基本的時間複雜度，也知道使用一些 Build-in Functions 時，如果沒有考慮時間複雜度會有怎麼樣的後果，例如 JavaScript 的 Array find() 函式就是一個 O(n) 的操作。

我們來聊聊更多基本但最常使用的資料結構，首先是 Array 各種操作的時間複雜度：讀取、搜尋、插入以及刪除。

知道這些操作背後的原理後，在寫程式時就可以確切地計算出某段程式碼的效率，避免因為資料量的線性增加，而造成執行時間呈指數暴漲。

Array 的操作

Array，中文稱作陣列，是所有程式語言最基本且常用的資料結構，用來放一連串的元素，每個元素有順序性，例如一個長度為 8 的整數 Array [30,22,19,37,4,12,1,10]。

而 Array 的實作原理是將記憶體中的一整塊位置保留下來，然後每個元素佔據一定的大小。一些中低階語言如 C, C++ 需要事先定義 Array 的長度和型態；而更高階的腳本語言像是 JavaScript, Python 則不需要，因為每個 Array 的元素可以是不同型態的，而且背後的實作可能用到更多的資料結構搭配而成，因此我們接下來僅就基本版的 Array 來探討。

讀取 Array 元素

下圖是一個長度為 8 的整數 Array，每個元素的大小是 4 Bytes，如果要讀取位置為 5 的元素，時間複雜度要怎麼計算呢？

由於每個元素的大小一致，我們可以準確的知道第 5 個元素的位置在 5 * 4 Bytes，也就是 20 Bytes 的位置。由於計算機只要知道記憶體位置就能迅速地找到目標，不用從頭到尾的走過一次，我們可以說只要常數時間就能讀到，時間複雜度為 O(1)。

*長度 8 的整數 Array

搜尋 Array 元素

而如果要搜尋這個 Array 中數字為 19 的元素是否存在，我們可以從最左邊位置為 0 的元素開始看，一路往右走訪，走到位置為 2 的元素時就找到了。

那麼時間複雜度為何呢？

我們在衡量時間複雜度的時候要考慮的是「最壞情況」，以搜尋操作來說，就是所有元素都看過都沒找到，或是在最後一個元素。那麼我們就走了 8 個元素，也恰好是這個 Array 的長度，所以長度 n 的 Array 就要走 n 個元素，其時間複雜度為 O(n)。

讀取和搜尋應該是最好理解的，再來看看其他 Array 的操作。

插入、刪除 Array 元素

先來分析插入一個元素到 Array 中的情況，如果我們要插入一個數字 20 到目前的 Array 位置 4 和 5 的中間，由於 Array 的長度固定，便需要做「擴容」的動作。

*Array 插入元素

先產生一個比原本長度長的 Array，然後再把原本 Array 中的元素複製過來，補上新的元素在我們指定的位置。

雖然有些狀況會是這個 Array 的長度還沒滿，我們又剛好插入到尾巴，但探討時間複雜度就要看最壞情況，因此這樣一番折騰後最終就會得到 O(n)。

刪除元素也是類似的道理，我們如果刪到中間的元素，為了不讓整個 Array 變得空空洞洞的，需要把後面的元素往前移動。

*Array 刪除元素

最糟的情況就是刪到第一個元素，後面就要每個元素都往前移動一格，這樣的情形也就和重新產生一個空的 Array 把每個元素都搬過來所需要花費的時間差不多，都是 O(n)。

總結來說，Array 的各種操作時間複雜度：
讀取 O(1)，搜尋、插入、刪除都為 O(n)

牛刀小試：購物車新增商品

理解了各種 Array 的操作所需要的時間複雜度，我們拿個例子實際操演看看。

假設我們要新增商品到一個資料結構為 Array 的購物車內，每次新增都要檢查購物車內是否有相同的商品，沒有的話便將商品插入到最前面的。

且看以下 JavaScript 的寫法：

const cart = ['Apple', 'Banana'];
addToCart('Carrot');

function addToCart(newItem) {
  for (const item of cart) {
    if (!cart.includes(newItem)) {
      cart.unshift(newItem);
    }
  }
}

我們在裡面用到了兩個 Built-in function：includes() 和 unshift()，其中 include() 會搜尋 Array 中是否包含特定元素，而 unshift() 會將商品插入在 Array 的最前面，兩者的時間複雜度都是 O(n)。

那麼，我們所寫的 addToCart() 函式要怎麼評估其時間複雜度呢？

我們明天來分析分析，並看看如何改進。