#cphb

每一次比較只能把「還有可能的排列」分成兩半 a < b ? b < c ? a < c ? 小於 大於 a b c a < c ? b a c b < c ? 小於 大於 小於 大於 a c b c a b b c a c b a 小於 大於 小於 大於 n! 片葉子 → 高度 ≥ log₂(n!) ≈ n log n → 最壞情況至少 n log n 次比較

排序是最便宜的結構:比較的下界、counting sort 與二分搜尋

· tech · 約 9 分鐘 · 📚 Competitive Programmer's Handbook 讀書筆記 #2

上一篇講的是看到 $n$ 就知道該寫什麼複雜度。這一篇講 CPHB 第 3 章:排序。原書這章很短,但它藏著一個我覺得比排序演算法本身更重要的觀念——排序不是目的,是在替後面的問題製造結構。 很多題目…

#algorithms#cphb#sorting#binary-search#book-notes

時限 1 秒 ≈ 數億次基本運算:看 n,反推能用的複雜度 輸入大小 n 可接受的複雜度 典型做法 運算量 n ≤ 10 O(n!) 試所有排列 10! ≈ 3.6×10⁶ n ≤ 20 O(2ⁿ) 試所有子集 2²⁰ ≈ 10⁶ n ≤ 500 O(n³) 三層迴圈 500³ ≈ 1.3×10⁸ n ≤ 5000 O(n²) 兩層迴圈、所有配對 5000² = 2.5×10⁷ n ≤ 10⁶ O(n log n) 或 O(n) 排序、掃一遍 10⁶×20 = 2×10⁷ n 很大 O(log n) 或 O(1) 二分搜尋、公式 — 例:n = 10⁵ 卻寫了 O(n²) → 10¹⁰ 次運算,要跑數十秒——還沒寫就知道不行

看到 n,就知道該寫什麼:時間複雜度與最大子陣列和

· tech · 約 10 分鐘 · 📚 Competitive Programmer's Handbook 讀書筆記 #1

開一個新系列:讀 Antti Laaksonen 的 Competitive Programmer's Handbook(CPHB)。這本書是 CSES Problem Set 的配套教材,線上 PD…

#algorithms#cphb#complexity#book-notes