iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 1
2
Software Development

使用JavaScript學習資料結構與演算法系列 第 1

Day1-來介紹一下資料結構和演算法吧!

  • 分享至 

  • xImage
  •  

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

資料結構是什麼?

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

那演算法又是什麼?

簡單的說它就是用於解決一個問題的一連串步驟,而它必須滿足幾項特性,這裡將用一個尋找[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


以上就是資料結構和演算法的基礎介紹!明天,我們將來了解陣列囉~/images/emoticon/emoticon12.gif


下一篇
Day2-陣列操作常用的20個函式
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言