跳至主要内容

演算法與資料結構是什麼？

演算法​

資訊

演算法是解決問題的方法

演算法是什麼？

許多人會聯想到社群平台的演算法，但那只能說是「內容推播演算法」。

更廣義地說，演算法是「解決問題的方法」。

簡單的問題如「將一堆數字依小到大排列」，複雜的問題如「找出從台灣大學到台北車站的最短路徑」，處理這些問題的方法都稱為「演算法」。

想了解更多，可以參考 TED-Ed 的影片：

複雜度​

資訊

複雜度用來比較演算法的優劣

電腦科學中，時常會用效能來比較優劣，包含處理速度的快慢還有資源的利用率等等，但是不同程式語言或不同的電腦，在處理同樣問題本來就會有快慢之分，要如何客觀比較好壞？

軟體層面，會利用複雜度來當客觀的衡量，無關乎用哪種程式語言、哪種機器。

在相同條件下，複雜度是用來衡量算法消耗多少時間與空間（記憶體）資源的度量標準：

  • 時間複雜度（Time Complexity）：演算法需要消耗的時間資源。
  • 空間複雜度（Space Complexity）：演算法需要消耗的空間資源。

電腦科學使用大 O 符號（Big O Notation）來表示複雜度。它只看「長期趨勢」，並忽略低階項和常數。

簡單的判斷方式，解法裡面有迴圈跑 n 次操作，時間複雜度就是 O(n)，如果迴圈裡面又有一個 n 次迴圈，那麼複雜度就是 O(n^2)。

如果解法有一個 array 來存 n 個東西，那麼空間複雜度 O(n)，即使儲存 3n 個東西，空間複雜度一樣是 O(n)，因為常數會被忽略。

舉例說明：從 1 加到 n 的總和​

題目：從 1 加到 n 的數字總和

第一種方法：迴圈

直觀的方法，迴圈從 1 跑到 n，把數字一路加上去。

function sumUp1(n) {
    let total = 0
    for (let i = 0; i <= n; i++) {
        total += i
    }
    return total
}

第二種方法：數學公式

直接用中學數學的公式，梯形公式去算等差數列總和。

function sumUp2(n) {
    return n * (n + 1) / 2
}

複雜度探討​

sumUp1 的複雜度

  • 時間複雜度：O(n)
    • 每一步要增加 i 的內容並把 i 加到 total 裡面，重複 n 次
  • 空間複雜度：O(1)
    • 用一個變數 (total) 來記錄

sumUp2 的複雜度

  • 時間複雜度：O(3) ~ O(1)，常數一律忽律倍數。
    • 有 3 個步驟：乘法、加法、除法
  • 空間複雜度：O(1)
    • 沒有另外使用變數

所以由此可見，sumUp2 數學公式的效率是比較好的。

資料結構​

資訊

資料結構是組織、儲存與管理資料的方式

如果把「資料」比喻成書本，資料結構可比喻成書架或抽屜。選擇不同的儲存方式，會直接影響到找書（搜尋）、放書（新增）和丟書（刪除）的速度。

如果你已經熟悉一門程式語言，那你肯定知道 Array，這就是一種資料結構。

其他學習資源：

最後於 更新