iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 1
2
Software Development

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

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

在開始用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. 有效性: 步驟清楚可行,能確實用數學運算出該步驟結果

在介紹演算法之後,要來介紹與它相關的兩個名詞:

空間複雜度(Space Complexity)

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

時間複雜度(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)

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): 對數

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


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


下一篇
Day2-陣列操作常用的20個函式
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言