載入中...

常見演算法設計策略分類

發表於2026-09-09|更新於2026-09-09|資料結構

|總字數:77|閱讀時間:1分鐘|瀏覽量:

看到這個 Algorithm	腦中直接想到
Prim	Greedy、MST
Kruskal	Greedy、MST
Dijkstra	Greedy、Single Source、不能負邊
Bellman-Ford	DP/Relaxation、Single Source、可負邊
Floyd-Warshall	DP、All Pairs
DFS	Cycle、Topo、SCC、Articulation、Bridge
BFS	Unweighted Shortest Path
Huffman	Greedy
0-1 Knapsack	DP
Fractional Knapsack	Greedy
Optimal BST	DP
LCS	DP
Matrix Chain	DP
Topological Sort	DFS / Indegree
SCC	DFS
Articulation Point	DFS + dfn/low

文章作者: YowDesert

文章連結: https://yowdesert.github.io/posts/65f4596b.html

版權聲明: 本部落格所有文章除特別聲明外，均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 YD's 學習筆記！

相關推薦

資料結構-Heap、Disjoint Sets

Heap MAX heap complete binary tree 父點要大於左右子點 Root為最大值 min heap 適合用Array保存 (因為compelete) Heap 優點 : Heap 適合實作 Priority Queue，可以在 O(1) 時間取得最大/最小值，且插入與刪除只需 O(logn)，並可用 Array 有效率地儲存。 Heap 操作中文意思時間複雜度為什麼 Insert X 插入元素 (O(log n)) 插入最後，再往上調整，最多走樹高 Delete-Max 刪除最大值 (O(log n)) 刪 Root 後，要向下 Heapify Heapify / Adjust 調整 Heap (O(log n)) 最差從 Root 一路調到 Leaf Find-Max 找最大值 (O(1)) Max-Heap 最大值就在 Root Build a Heap (Bottom-Up) 建立 Heap (O(n)) ⭐ Bottom-Up Heapify Decrease Key（Min-Heap）降低...

資料結構 - 各種資料結構優點

各種資料結構優點整理1. Array優點可以透過 index 直接存取元素 Random Access 很快記憶體連續，效率高適合已知大小、常做查詢的資料時間複雜度 Access: O(1) Search: O(n) Insert/Delete: O(n) 適合頻繁用 index 查資料 Heap Matrix Dynamic Programming table 一句話記憶 Array：查位置很快，插刪較慢 2. Linked List優點不需要連續記憶體插入、刪除方便不需要搬動其他元素大小可以動態改變時間複雜度 Access: O(n) Search: O(n) Insert/Delete: 已知位置：O(1) 找位置：O(n) 適合常做插入、刪除資料數量經常改變一句話記憶 Linked List：插刪方便，但不能直接跳到某個位置 3. Stack特性LIFO Last In First Out 後進先出優點 Push / Pop 都很快適合處理「最近加入的資料」很適合遞迴、括號匹配、Expression 時間複雜度 P...

資料結構 - Advanced Tree

Double-Ended Priority Queue Operation Time Complexity Insert x O(log n) Delete-Min O(log n) Delete-MAX O(log n) Find min or MAX O(1) Double Priority Queue Insert(x)：插入任意元素 Delete-Max：刪除最大值 Delete-Min：刪除最小值 min-Max Heap complete Binary Tree 每層交替 min level -> MAX -> min -> MAX -> … min 是整個 subtree 裡最小的 MAX 是整個 subtree 裡最大的 insertion x 置放於last node之後令 x 父點為 p P 位於 min : 1234567// 若插入點在 max 層，即代表父親位於 min 層if(x<H[p]){ // x 若比父點小 H[n] = H[p]; /...

資料結構 - 所有 Tree 整理

Tree 總整理一、各種 Tree 關係圖 123456789101112131415161718192021222324252627282930Tree│├── Binary Tree│ ││ ├── Full Binary Tree│ ├── Complete Binary Tree│ │ └── Heap│ │ ├── Min Heap│ │ └── Max Heap│ ││ ├── Binary Search Tree (BST)│ │ ││ │ ├── AVL Tree│ │ ├── Red-Black Tree│ │ └── Splay Tree│ ││ └── Huffman Tree│├── Multi-Way Search Tree│ ││ └── B-Tree│ ├── 2-3 Tree│ ├── 2-3-4 Tree│ └── B+ Tree（B-Tree 的變形）│└── Heap 類 ├── Binary...

資料結構 - Search and Sort

Search and SortSearchLinear(Sequential) Search 由左至右一一比較 Time Compexity : $O(1)$ Binary Search 資料要先排序需要保存在 Array Time Compexity : $O(log n)$ 方法每次都與中間比較相等 : 找到 x < 中間值 : 在左半部再做一次 x > 中間值 : 在右半部再做一次 Sort Internal Sorting : 資料量很小，可以全部放在Memory中 External Sorting : 資料量太大，需要藉助外部儲存體常見External Sort : Merge Sort(也可以搭配Sellection Tree)、M-Way Tree、B Tree、B+ Tree Stable and unStable Input Data : …,K,…,K+,… OutPut Data保證結果為…,K,K+,… 則為Stable UnStable Sort會比Stable多不必要的資料交換例子 : Stable Sort...

資料結構 - 高等樹-題目注意

Double Priority Queue Insert(x)：插入任意元素 Delete-Max：刪除最大值 Delete-Min：刪除最小值 SMMH : left sibling <= right sibling (同一個爸爸的兩個子點) 如果沒有兄弟就不用比如果 node x 有祖父，則祖父的左子點必定 <= X 如果 node x 有祖父，則祖父的右子點必定 >= X Deap : 才是跟隔壁家兄弟比一個BT的左子樹與右子樹皆為AVL Tree，那這個樹不一定是AVL Tree 把BST 轉成 AVL Tree -> 花費 $O(n)$ 次Rotation 1234567891 \ 2 \ 3 \ ... \ n Blanced BST 花 $O(Log n)$ 在刪除一個key 找到key : $O(Log n)$ 刪除加調整 : $O(Log n)$ 2-3 Tree 高度 h 有幾個點最少 : $2^h - 1$ 最多 : $3^h - 1 / (-...