💡一句話定義
O(n²)＝ 運算量隨輸入規模 n 的平方成長：n 變 10 倍，運算量約變 100 倍。自注意力要讓每個 token 對序列中所有 token算關注，n 個 token 就是 n×n 次，計算與記憶體都是 O(n²)——這是長上下文的主要瓶頸。
🔗為什麼「兩兩比對」是 O(n²)？
🎮互動：拖動 n，看連線爆炸
拉動滑桿改變 n：左圖每條線代表一次比對，右圖比較 O(n) 線性（藍）與 O(n²) 平方（紅）的增長。留意 n 一過十幾，左圖就變成「密不透風的紅網」。
為什麼兩兩比對的時間複雜度是 O(n²)？
兩兩比對連線圖 (每條線代表1次比對)
運算量增長曲線
系統狀態：完全沒有負擔
目前數量很少，系統瞬間就能計算完畢。
🤖這跟 Transformer 有什麼關係？
自注意力裡，每個位置都要對所有位置算一次注意力分數——這正是「兩兩比對」。序列長度 n 的注意力矩陣是 n × n，所以計算與記憶體都是 O(n²)。這就是為什麼上下文視窗有上限、處理長文件／長對話這麼貴：把上下文加長一倍，注意力成本會變成約四倍。
📈O(n) vs O(n²)：數字有多可怕
| n | O(n) 約 | O(n²) 約（兩兩比對） |
|---|---|---|
| 10 | 10 | 45 |
| 100 | 100 | 約 5,000 |
| 1,000 | 1,000 | 約 50 萬 |
| 100,000 | 10 萬 | 約 50 億 |
易混：O(n²) 講的是隨「輸入序列長度 n」的成長，跟「模型參數量」是兩回事，別搞混。
🚀怎麼降低注意力的複雜度
🧱稀疏注意力
只算部分位置對（如局部＋少數全局），降到近線性。
只算部分位置對（如局部＋少數全局），降到近線性。
📏線性注意力
用核技巧改寫，讓複雜度接近 O(n)。
用核技巧改寫，讓複雜度接近 O(n)。
🪟滑動視窗
只關注鄰近固定範圍，長序列友善。
只關注鄰近固定範圍，長序列友善。
⚡FlashAttention
不改複雜度但大幅省記憶體、加速實際運算。
不改複雜度但大幅省記憶體、加速實際運算。
✅自我檢測
Q1. O(n²) 是什麼意思？
運算量隨輸入規模 n 的平方成長。n 變 10 倍，運算量約變 100 倍。兩兩比對 n(n−1)/2 次就是典型的 O(n²)。
Q2. 為什麼自注意力是 O(n²)？
每個 token 都要跟序列中所有 token 算注意力分數，n 個 token 形成 n×n 的注意力矩陣，計算與記憶體都是 O(n²)。
Q3. O(n²) 為什麼是長上下文的瓶頸？
序列一長，計算與記憶體平方暴增（長度加倍→成本約四倍），限制了上下文視窗長度與長文處理的成本。
Q4. 有哪些降低注意力複雜度的方法？
稀疏注意力、線性注意力、滑動視窗等把複雜度降到近 O(n)；FlashAttention 不改複雜度但大幅省記憶體、加速實際運算。
🎯重點整理
- O(n²)：運算量隨 n 平方成長，n 變 10 倍→約 100 倍。
- 兩兩比對：n(n−1)/2 ≈ n²/2 次。
- 自注意力：每個對所有算注意力 → n×n → O(n²)。
- 瓶頸：長序列成本暴增，限制上下文視窗。
- 解法：稀疏／線性注意力、滑動視窗、FlashAttention。