5. 算法设计方法¶
算法设计的方法有许许多多，根据算法界的第一神书《算法导论》，可以分为五种基本类型：贪心法、分治法、动态规划法、回溯法和分支限界法，常被尊称为五大算法。算法设计方法不同于我们在前面学过的前缀和、差分法、递归、二分法、深搜、宽搜等具体的算法技巧，而是设计算法的思路和方法。
简单的问题往往用一种方法设计出一个算法就可以解决，有些复杂的问题则需要同时用到多种设计方法，结合多种算法技巧来设计出一套精细复杂的算法来解决问题，还有一些问题则到目前为止人类还没有找到有效的算法。
一个优秀的算法，必须同时关注存储空间的使用量和完成运算的时间量两个指标，通常称为空间复杂度和时间复杂度。二者往往会出现相互矛盾对立的情况，为了加快算法运行的速度有时候就需要使用更多的存储空间，而有时候为了减少空间使用则不得不使算法运行时间延长。优秀的算法会综合考虑二者，取一个最佳的平衡点。
考虑运行速度的时候，我们称不超过多项式时间复杂度的算法为有效算法。非常高效的算法包括常数（即0阶多项式）时间 \(O(1)\) 算法、对数时间 \(O(\log n)\) 算法、线性（1阶多项式）时间 \(O(n)\) 算法、\(O(n\log n)\) 算法。尤其是在算法竞赛时，上述这些时间复杂度往往是要追求的目标。有些 \(O(n^2)\)、\(O(n^2\log n)\) 甚至少部分 \(O(n^3)\) 时间的算法也可能在OJ或竞赛中被接受，但大多数情况下2阶多项式及以上的算法就大概率要TLE了，3阶多项式以上的基本上没可能过关。
但是在实际的算法设计领域，只要是多项式时间 \(O(n^m)\) 算法，无论阶多大，只要它是一个有穷的确定的阶，就被认为是一种有效的算法。而那些目前还没有多项式时间算法的问题，则被称为NP-hard问题，或NP难题，被认为是目前无法有效求解的问题。已知的NP难题已经有数千个，在各种应用领域都广泛存在。
NP难题目前没有多项式时间的有效算法，但同时目前也无法证明它们确实不存在多项式时间的有效算法。而且它们相互之间具有等价性，如果某一个具体的NP难题被解决了，找到了多项式时间的算法，或者证明了它可以有多项式时间的算法，那就意味着大量的其他NP难题也都被证明了可以有多项式时间的算法。另外还有一类特殊的NP难题，是所有NP难题中最难的一类，称为NPC问题或NP完全问题，最经典的莫过于旅行商问题（又叫货郎问题）。只要有一个NPC问题被解决就意味着所有的NP难题都可以有多项式时间的有效算法。所以，“NP难题能否在多项式时间内解决”这个问题就成为了著名的数学七大千禧难题之一，简称P=NP?，是无数的数学家、计算机科学家竞相追逐的目标。
尽管NP难题目前还没有一个找到有效的多项式时间算法，但这并不代表着这些问题就彻底无解。很多问题在一些特定条件下是可以有效求解的，有些问题可以在多项式时间内求出一个比较靠谱的较优解，还有很多问题可以用一些近似算法、随机算法来求出尽量好的近似解，比如模拟退火、遗传算法等等。关于NP难题的这些问题我们在第6章高级算法部分再去讨论。本章主要介绍贪心法、分治法、动态规划和解搜索这四类最常见的算法设计方法。