第 9 页

进阶结构专题

并查集只加"按秩合并"就从 5091ms 掉到 4.2ms（1200 倍），再加路径压缩反而没变快；线段树懒标记与朴素实现查询结果逐位相同；LRU 用 list+哈希 100 万次操作 134ms。

中间插入 10 万次 list 比 vector 快 216 倍，可反转整个表时 vector 又赢 18 倍，遍历差 33 倍——"数组好还是链表好"没有答案，只有工作负载的答案。

n 翻倍耗时到底变几倍、二分在 100 万元素上只要 20 次比较、vector 扩容的 131071 次搬移怎么摊成 1.31、同样 O(n²) 的两种写法差 13 倍——用数字代替直觉。

斐波那契 n=40 朴素递归 196.9ms vs 迭代 0.0001ms；背包一维滚动写成正序时，有 23% 的随机用例结果"碰巧正确"；二维降到滚动数组是 62.5MB 变 31KB。

200 万条边的实测：CSR 建图比 vector<vector<int>> 快 7.4 倍、内存省 3 倍；邻接矩阵要 596MB 而邻接表只要 7.6MB；递归 DFS 在 10 万层崩溃而迭代版跑完 500 万层。

4000 组随机币制实测贪心找零有 16.3% 的金额算错；N 皇后位运算版快 10.7 倍且解数与已知值完全一致；区间调度换成"按开始时间"就从 3 变 1。

200 万次查找实测 unordered_map 110.6ms、sorted vector 542.7ms、map 2512.3ms；键步长为 4 时低位散列只用 25% 的桶；空桶率 21.6% 才是正常状态。

手写堆的两个比较方向都写反了、30 万次随机操作对拍才抓出来；双堆求流式中位数比每次重算快 3862 倍；k 路归并理论更优却比"拼接再排序"慢 43%。