分类:算法

算法是解决一类问题的有限步骤。读算法时，先明确允许的输入和所求的输出，再核对步骤是否会停、答案是否正确，最后计算时间与额外空间。算法与复杂度用一个完整的找最大值例子说明这些基本问题；下列词条把同一读法用于不同对象。

• 有序数据：二分查找在已经排序的数组里找分界。它不同于用函数值异号来求根的二分法。
• 文本中的模式：KMP字符串匹配用模式自己的前后缀关系在失配后继续扫描，不把文本读头倒回去。
• 图上的移动：先在图论中认清顶点、边和路径，再对照广度优先搜索的逐层扩展与深度优先搜索的深入回退。最短路径讲边权与松弛，A星搜索算法进一步利用有条件的剩余费用估计。
• 重排与选取：归并排序用稳定的归并保留相等关键字的顺序；快速排序划分后还要排两侧，快速选择只追踪目标名次所在的一侧。动态规划沿前缀填表，0-1背包问题再把状态换成物品数与剩余容量。
• 连续与约束：牛顿法借切线迭代求根，但需要局部条件；线性规划描述可行域与最优性，单纯形法在其顶点之间改进方案。

• 算法与复杂度
• 二分查找、KMP字符串匹配、二分法
• 广度优先搜索、深度优先搜索、最短路径、A星搜索算法
• 归并排序、快速排序、快速选择
• 动态规划、0-1背包问题
• 牛顿法、单纯形法

每一篇的复杂度都要与具体任务、输入规模和基本操作一起读。学科导航列出其他领域入口，学习路径给出适合连读的顺序。