算法概览
算法选型从输入、约束和结果开始。订单需要按时间展示,是排序;从已排序记录里定位一个时间点,是搜索;给一批任务分配有限预算,则需要先判断选择之间是否相互影响。名称相似的算法可能有不同前提,先把问题模型说清,再比较复杂度。
先把业务问题变成可检查的模型
以订单系统为例,“查询很慢”还不足以决定算法:是每个客户都重扫全部订单,还是记录已排序却仍从头找,或者真正耗时的是磁盘读取?先固定样例输入、期望输出和规模,分开测量计算与 I/O,才能定位该改哪一段。
| 需要解决的问题 | 通俗例子 | 判断前提与入口 |
|---|---|---|
| 评估增长速度 | 客户和订单各翻倍,工作量如何变化 | 明确多个独立规模,见复杂度分析 |
| 重新排列记录 | 订单按时间展示,相同时间保持原顺序 | 是否要求稳定、有无内存上限,见排序 |
| 定位目标或边界 | 找第一笔不早于指定时间的订单 | 数据是否有序、查询是否重复,见搜索 |
| 有限资源下做选择 | 预算只能覆盖部分任务,怎样使总收益最高 | 状态能否概括后续所需历史,见动态规划 |
| 逐步选当前最佳 | 在单会议室内安排尽量多场互不重叠的会议 | 必须证明局部选择安全,见贪心 |
| 枚举并撤销选择 | 找出满足依赖和冲突限制的排班 | 分支规则、剪枝是否保留所有合法解,见回溯 |
| 拆成更小的同类问题 | 两半记录各自排序,再合并 | 子问题规模和合并成本,见分治 |
| 处理对象之间的关系 | 部署依赖排序、道路最短路径 | 有向或无向、有无负权及环,见图算法 |
| 匹配或比较文本 | 日志查关键字、计算两段文本的编辑距离 | 编码、匹配单位、模式数量,见字符串算法 |
| 处理整数与数值关系 | 计算最大公约数、快速模幂、采样 | 精度、范围与随机性合同,见数学算法 |
这些分类不是互斥目录。编辑距离属于字符串问题,也常用动态规划求解;归并排序使用分治;广度优先搜索用于无权图最短路。阅读时先找业务对象和约束,再沿链接了解对应机制。
排序一次,还是查询时逐条扫描
如果只在 20 条记录中找一次目标,线性扫描通常足够。面对 100 万条记录和持续到来的查询,可以评估排序后建立边界查找,或构建索引。不要只比较单次查找的 O(n) 与 O(log n),还应计入预处理、更新和内存成本。
“哈希查找平均 O(1)”也不表示任何键、任何输入都恒定耗时。长字符串的散列和比较、哈希冲突、缓存命中与数据加载都会影响代价。数据本来在数据库中时,应先检查查询计划和索引,不能把全表读回应用再套算法当作默认优化。
贪心、动态规划与回溯怎样分工
有 5 个预算单位,任务 A 花费 2、收益 3,B 花费 3、收益 4,C 花费 4、收益 5,每项只能做一次。只挑收益最高的 C 得 5;选择 A 和 B 得 7。这说明“当前收益最大”在这个模型中不保证总收益最大。
动态规划把“前 i 个任务、剩余或可用预算”作为状态,避免同一子问题重复求解。回溯逐项尝试选或不选,可以直接枚举可行组合,适合规模较小或约束难以压缩的情况。贪心只有在证明某种选择不会破坏最优解后,才能作为正确解法;加上一个排序步骤并不自动得到这个证明。
结果也应讲清范围:求最大值、找任意一个可行解、恢复一个最优方案、列出所有方案,可能需要不同的存储与时间预算。“能算出分数”不等于“能还原任务清单”。
结果、资源和规模一起验收
先用小规模的直接实现或手算结果做基准,再与优化算法对比。对排序检查顺序、元素数量和重复值;对路径检查可达性、路径权重与负权前提;对动态规划检查边界和所选方案是否满足约束。空输入、重复值、最大数值和不可达情况都要进入样例。
正确性通过后,再测量多组规模、辅助内存、递归深度和 I/O。指数级枚举不因加缓存就必然变成多项式算法;伪多项式的背包表也可能因预算数字巨大而无法分配。工程中优先使用语言标准库或成熟算法库,自写实现用于理解机制、满足明确的特殊合同,并用对照样例验证。
建议从复杂度分析进入排序和搜索,再按任务需要读选择类、关系类或文本类算法。每一篇都应回答输入假设、过程、结果和失败边界,读完后能用小例子解释一次真实执行。
