一、问题——算法——程序
- 问题：一个函数，从输入到输出在一种映射
- 算法：对特定问题求解过程的描述，是指令的有限序列
- 程序：算法在计算机程序设计语言中的具体实现
二、算法的特性
- 通用性：参数化的，能对一类问题进行参数化输入并问题求解
- 有效性：有限条有效指令组成的指令序列，保证计算结果的正确性
- 确定性：算法的下一步执行步骤必须明确
- 有穷性：执行必须在有限步内结束，不能有死循环
三、基本算法分类
- 穷举法：
遍历每一个元素，比较低效，但是是一种万能的算法；对于一个问题，如果一时想不出好的算法的话，可对小规模数据采用穷举法剖析问题的特性和数据的特性，进而寻求更高效的算法 - 回溯、搜索：
能进则进，不能进则换，不能换则退，如树和图的遍历 - 递归分治：
二分查找，以及快速排序、归并排序，都是经典的分治算法思想 - 贪心法：
其数据具有贪心性质，每次求解的时候都采用当前的最佳解，最终得到最优解，如 Huffman 编码树、最短路径 Dijkstra 算法、最小生成树 Prim 算法 - 动态规划：
得到小规模问题的最优解，然后在更大规模的时候去组合这些最优解，最后得到全局的最优解，如图的两两结点之间最短路 Floyd 算法。要求具有最优子结构性质以及无后效性，动态规划的子结构有重叠，而递归分治子结构不重叠。
四、“监视哨”顺序检索
设置“监视哨”后，在查找过程中不用判断 i 是否越界，少一次判断，算法的运行效率会更高