YD's 學習筆記

看到這個 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

資工研究所常見演算法時間複雜度整理 版本：2026-09-09 語言：繁體中文（zh-TW） 定位：資工研究所入學考、演算法／資料結構課程、口試與複習速查 主要依據：CLRS、原始論文、Princeton Algorithms、MIT OpenCourseWare、CP-Algorithms、GeeksforGeeks；中文資源列於文末供交叉複習。 Executive Summary 這份整理的核心不是只背一張 Big-O 表，而是辨認「複雜度成立的前提」。同一個演算法可能因資料表示、輔助資料結構、輸入分布、是否允許提早停止、字母表大小，甚至雜湊碰撞模型而有不同界限。研究所考題常用這些前提製造選項差異，因此表格同時標示最佳／平均／最壞、輔助空間、穩定性、in-place 與使用條件。 最值得優先記憶的骨架如下： 比較式排序下界：一般 comparison sort 的最壞情況需要 (\Omega(n\log n)) 次比較；Merge Sort 與 Heap Sort 保證 (O(n\log n))，Quick Sort 平均／期望 (O(n\log n)) 但最壞 (O(...

CPU產生的是Logical Address，Memory -> Physical Address Memory 真正使用的是Physical Address 中間用MMU轉換 對程式來說是看Logical Address，所以如果實際RAM只有1GB，程式也可以是4GB Binding 時機 位址什麼時候確定 Logical = Physical？ Compile-time 編譯時 ✅ Load-time 載入 RAM 時 ✅ Execution-time 執行過程中才轉換 ❌ TLB (Translation Look-Aside Buffer) 本質上是Page Table的高速 硬體 Cache Base = 1200 ， Limit = 350 => 1200 ~ 1549 (limit - 1) Two Level Paging ， 需要 2 次 M.A. 才能轉成Physical Address Outer Page Table Inner Page Table 如果真的要拿資料 需要第3次 Dy...

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...

Single Resource RAG : Cycle <=> Deadlock 但是多個Resources 不一定 DeadLock 要成立 要四個條件達成 Mutual Exclusion Hold and wait No Preemptive Circuler Wait Deadlock Prevention 通常不會去破壞 Mutual Exclusion 因為有些資源天生就不能給兩個使用 甚麼時候Run DeadLock Detection 隔一段時間 系統回應變慢 事件等待太久 CPU utilization 太低 Deadlock Prevention 定期檢查wait-for Graph -> 這個不是Prevention 每次分配前都先確認是不是Safe State DeadLock Safe/Unsafe 是用在 DeadLock Avoidance 不是 Prevention DeadLock 4個條件是 必要條件 必要條件 : B 要發生時 A一定要存在 : B => A 充分條件 ...

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...

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 / (-...

Ordered-Linked-List 就算有排序也不能直接Binary Sort 兩個Array，大的n個，小的m個，要找兩個有沒有相同的 => $O(nlogm)$ m Array 先 Sort => O(mlogm) 把 n Array從頭跑到尾，並且在m Array Binary Search => O(n)*O(logm) = $O(nlogm)$ Singly Linked List 最適合使用 Insertion Sort 可以減少Data Movement Array → Random Access 很強 → Quick Sort / Heap Sort 很方便 Linked List → 插入、合併很強 → Insertion Sort / Merge Sort 很方便 在限定使用Comparison-Based Skill 情況下，最快 $O(n log n)$ 如果沒有這個限制最快到 $O(n)$ Q : All Sorting Method 最快可到達 $\omega(n \log n)$ : False EX ...

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]; /...

I/O Device Queue 是OS管理的 Timer 不在PCB裡 ， 他是用來產生Interrupt的，不是CPU使用時間資訊 Which Schedulers can be used to control the degree of multiprogramming? 問誰可以增/減Memory的Process Job Scheduler(Long Term) : 看誰要進Memory、Medium-Term Scheduler : Swapper to Disk Job Scheduler = Long-Term Scheduler CPU Scheduler = Short-term Scheduler Disk scheduler => Disk I/O request 哪一個先處理 Printing 表 I/O 完成了 (A)Synchronous I/O 類型 發出 I/O 後 Synchronous I/O 等 I/O 完成再繼續 Asynchronous I/O 不用等完成，可以先做其他工作 ...