單元地圖

¶前置知識

• ✓ 運算量估計與 10^9 法則（上冊 4.9）
• ✓ O 記號與「認 O、代 n、除以 10^9」估 TLE 三步驟（下冊 10.1）
• ✓ 陣列與 vector（上冊第六單元、下冊 10.2、10.3）
• ✓ 函式（上冊第七單元）
• ✓ 等差級數（上冊 0.4 的學前數學）

¶學習成果

本單元結束後，你將能夠：

• ✓ 說出「優化＝改變運算次數成長的形狀」，判斷一個做法該修還是該換
• ✓ 用數學公式把 O(n) 的累加變成 O(1)
• ✓ 用「索引當數字」的標記陣列把查詢變 O(1)，實作 mex 函數
• ✓ 用「因數成對」把質數判斷加速到 O(\sqrt{n})，並包成函式回答多筆詢問
• ✓ 對「每輪減半」的過程算出總量，寫出 O(n) 的約瑟夫模擬
• ✓ 說出 \log n 的直觀意義（一直除以 2，除幾次會到 1），看懂 O(\log n) 與 O(n \log n)
• ✓ 用改變枚舉順序＋整除計數，解 A*B*C 這類「數三元組」的題目