算法分析中，平攤分析尋找在最壞情況下的操作序列中每操作的平均耗費時間。這個方法需要知道操作序列中可能發生的每個操作。通常應用在操作間存在狀態的資料結構中。基本思想是，一個最壞情況操作會改變狀態而不會在一段時間內再次出現，因此「平攤」它的耗費。

Chapter 5  網路流 Network Flow 5.1  網路流  Network Flow 網絡流 (Network Flow) 是指在一個每條邊都有容量 (Capacity) 的有向圖分配流，使一條邊的流量不會超過它的容量。邊有附帶容量的圖稱為網...

個人覺得考這種 $T(n) = T(n+-*/)$ 啥啥的題目很沒意義，可是一堆教授喜歡考，所以整理這個表，希望大家看到求遞迴複雜度的題目都真的可以5秒內拿分，珍惜生命，請了解原理後使用速解法！ # 這裡假設大家對 Algorithm 聖經本的 Recursive tr...

Chapter 3   貪婪演算法  Greedy Algorithm 3.1   貪婪演算法 簡介 貪婪演算法(Greedy algorithm)是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體上最優(global optimization)加以考...

Chapter 4   Graph Algorithm 4.1   Minimum Spanning Trees Spanning Tree 定義 S = (V, F)為G的一個Spanning Tree且S滿足 自F’中任取一邊加入S中必形成Cycle ...

Chapter 2  動態規劃 Dynamic Programming 2.1   動態規劃簡介 動態規劃(Dynamic Programming)是指將一個較大的問題定義為較小的子問題組合，先處理較小的問題並將結果儲存起來(通常使用表格)，再進一步以較小問題的解逐步建...

Chapter 6   NP-Completeness 6.1   P、NP、NP-Hard、NP-Complete P、NP、NP-Hard、NP-Complete這些概念都是用來描述一個問題的難度。也就是一個問題能否在以上時間內求解，或者驗證一個解是否符合一個問題。...

Chapter 1  漸近表示法、遞迴與複雜度 Asymptotic Notation, Recurrences and Complexity 1.1  漸進表示法 Asymptotic Notation 時間複雜度是指完成演算法所需的時間，一般為輸入資料量 $n$ 的...