演算法與資料結構是什麼？
演算法
演算法是解決問題的方法
演算法是什麼？
許多人會聯想到社群平台的演算法，但那只能說是「內容推播演算法」。
更廣義地說，演算法是「解決問題的方法」。
簡單的問題如「將一堆數字依小到大排列」，複雜的問題如「找出從台灣大學到台北車站的最短路徑」，處理這些問題的方法都稱為「演算法」。
想了解更多，可以參考 TED-Ed 的影片：
資料結構
資料結構是組織、儲存與管理資料的方式
如果把「資料」比喻成書本，資料結構可比喻成書架或抽屜。選擇不同的儲存方式，會直接影響到找書（搜尋）、放書（新增）和丟書（刪除）的速度。
如果你已經熟悉一門程式語言，那你肯定知道 Array，這就是一種資料結構。
複雜度
複雜度用來比較演算法的優劣
電腦科學中，時常會用效能來比較優劣，包含處理速度的快慢還有資源的利用率等等，但是不同程式語言或不同的電腦，在處理同樣問題本來就會有快慢之分，要如何客觀比較好壞？
軟體層面，會利用複雜度來當客觀的衡量，無關乎用哪種程式語言、哪種機器。
在相同條件下，複雜度是用來衡量算法消耗多少時間與空間（記憶體）資源的度量標準：
- 時間複雜度（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，把數字一路加上去。
- Python
- JavaScript
- Java
def sum_up1(n):
total = 0
for i in range(n + 1):
total += i
return total
function sumUp1(n) {
let total = 0
for (let i = 0; i <= n; i++) {
total += i
}
return total
}
class Solution {
public static int sumUp1(int n) {
int total = 0;
for (int i = 0; i <= n; i++) {
total += i;
}
return total;
}
}
第二種方法：數學公式
直接用中學數學的公式，梯形公式去算等差數列總和。
- Python
- JavaScript
- Java
def sum_up2(n):
return n * (n + 1) // 2
function sumUp2(n) {
return n * (n + 1) / 2
}
class Solution {
public static int sumUp2(int 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 數學公式的效率是比較好的。
學習地圖：新手該從哪裡開始？
DSA 的主題很多，內容彼此又有前後關聯，如果沒有頭緒，可以參考下面的順序：
- 打好基礎觀念
- Recursion：非常多資料結構與演算法都建立在遞迴的概念上，務必先搞懂。
- Divide and Conquer：遞迴最重要的應用框架之一，後面的 Sorting、Quickselect 都會用到。
- Bit Manipulation：了解數字在電腦裡的二進位表示，之後遇到位元運算相關的技巧不會慌。
- 從最貼近生活的線性資料結構入手
- 進入階層與網狀結構
- 搭配資料結構學習核心演算法
- 進階解題策略
不需要一次把所有主題都讀完才開始刷題。建議每學完一個主題，就馬上去 LeetCode 找幾題對應分類的題目練習，邊刷邊回來對照筆記，印象會更深刻。
其他學習資源：