复杂度上限与性能预算¶

目标：把“会写出正确答案”升级成“会在目标规模下写出能通过面试和线上评测的答案”。

一、先看输入规模，再选复杂度¶

输入规模	常见可接受复杂度
`n <= 20`	`O(2^n)`、`O(n!)` 可能可接受
`n <= 200`	`O(n^3)` 勉强，优先 `O(n^2)`
`n <= 1e3`	`O(n^2)` 常见上限
`n <= 1e5`	`O(n log n)` 或 `O(n)`
`n <= 1e6`	通常需要 `O(n)` 或更优

这不是绝对规则，但足够作为刷题和面试的一线判断。

二、算法题里最常见的“复杂度失手”¶

把每次查询都线性扫描
滑动窗口里重复扫描窗口内部
在循环里排序
数据流问题每次都整体重排
树/图题重复遍历同一子结构

三、面试时应该怎么表达¶

推荐表达模板：

Text Only

输入规模到 1e5，因此我先排除 O(n^2)；
目标应该是 O(n log n) 或 O(n)。
如果需要在线更新，就优先考虑堆、哈希表、单调队列、平衡结构。

四、常见题型的性能预算¶

题型	默认目标
Top-K	`O(n log k)`
滑动窗口	`O(n)`
区间合并	`O(n log n)`
图遍历	`O(V + E)`
数据流中位数	插入 `O(log n)`、查询 `O(1)`
LRU / Trie 设计题	单操作均摊 `O(1)` 或 `O(log n)`

五、刷题时的强制自检¶

写完代码前先问自己：

当前复杂度是多少？
是否能匹配输入规模？
是否存在明显退化输入？
有没有更合适的数据结构？

如果这四个问题回答不清，通常还没有到“面试可交付”的水平。