一起动脑筋 · 先看一个小故事
机器人反复计算同一周前几天的总页数。女孩说：“算过的结果能不能先记下来？”
把过程摊开来看
- 先观察哪里重复最多
- 复用结果保存累计量
- 检查正确与原方法比较
- 测量相同输入下计时
优化先找真正耗时的地方，再减少重复工作或换合适算法。
对重复区间求和，前缀和能帮助复用计算；对其他任务则要找到对应的结构。
01程序慢了，第一反应应该是什么？
先不要急着“加各种优化”。
先找到真正慢在哪里
可能是算法太慢，也可能是 I/O、内存访问、重复计算或其他原因。
02方法一：减少重复计算
如果同一个结果反复计算，可以考虑预先保存。
前缀和就是典型例子：先 O(n) 预处理，之后区间和查询 O(1)。
03方法二：换更合适的算法
顺序查找
O(n)
有序数据二分查找
O(log n)
但前提是数据满足二分需要的条件。
04方法三：换数据结构
如果程序总是在队头取元素，用合适的队列比频繁移动整个数组更自然。
如果需要快速按键查找，可能会考虑哈希表等结构。
05方法四：剪掉不可能的搜索
搜索时，如果某条分支已经确定不可能得到答案，就没必要继续深入。
检查当前状态→确定不可能→提前停止这条分支
这种思想叫剪枝（pruning）。
06方法五：减少不必要的 I/O
算法题中，大量逐字符或频繁刷新输出也可能拖慢程序。
不过 I/O 优化应建立在真的存在瓶颈时，而不是无脑套模板。
07为什么不能只靠“代码写短一点”？
代码行数少不代表执行工作量少。
std::sort(a.begin(), a.end());虽然只有一行，但内部仍会执行复杂算法。
08优化后怎样确认真的更好？
复杂度分析
判断增长趋势。
正确性测试
不能为了快把答案改错。
实际测量
真实环境下用计时或 profiler 检查。
09最重要的优化原则是什么？
你已经知道了什么
- 优化前应先找到瓶颈。
- 减少重复计算、换算法、换数据结构都可能提速。
- 搜索可以通过剪枝减少无效状态。
- 代码更短不等于运行更快。
- 优化必须同时保证正确，并用复杂度和实际测量验证。
本专题完成：下一专题进入“信奥解题思维”。
轮到你来试一试
只改变量名会让原来一百万次重复加法消失吗？
想好了吗？点开看解释
不会。需要改变实际工作量或实现瓶颈，并用相同测试条件验证。