演算法圖鑑Algorithm Atlas

演算法 · 4 個細項

Divide & Conquer分治

分治是 O(n log n) 的來源：把問題切半、遞迴解決、合併結果。合併排序與快速排序是它最有名的例子，這裡把它當成通用方法來學，並用 Master Theorem 算複雜度。

為什麼要學 Divide & Conquer

現實中的應用

為什麼切一半就能變快

n 個東西兩兩比要 n² 次，但切成兩半各比再合併，只要 n log n。Master Theorem 讓你不用每次都手推遞迴式。

→ 對應課程：Master Theorem

加密與大數運算

RSA 要算 a 的幾百位次方再取模，快速冪把指數切半，幾百次乘法就完成，不然算到宇宙毀滅。

→ 對應課程：Fast Exponentiation

統計「有多少對是反的」

評分系統要算兩份排名差多遠，本質是逆序對數量。在合併排序的合併步驟順便數，n log n 就好。

→ 對應課程：Count Inversions

細項

4 篇

#演算法複雜度難度狀態

01Master Theorem 遞迴式求解T(n) = aT(n/b) + f(n) 的三種情況用在：快速判斷分治演算法的複雜度—空間 —可學習 02Maximum Subarray 最大子陣列分治版與 Kadane 線性版的對照用在：股票最佳買賣區間、訊號分析O(n log n) / O(n)空間 O(log n)可學習 03Fast Exponentiation 快速冪指數切半，遞迴或位元迭代用在：RSA、模運算、矩陣快速冪算費氏O(log n)空間 O(1)可學習 04Count Inversions 逆序對在合併排序的合併步驟計數用在：排名相似度、資料「有多亂」的度量O(n log n)空間 O(n)可學習