本篇博文对常见算法进行总结和整理,内容安排遵照CS-341 Algorithms @ Waterloo University。
一、时间复杂度
衡量算法好坏的标准便是它的时间和空间复杂度,常用的是时间复杂度。我们将算法中基本操作重复的次数表示为问题规模n的某个函数g(n)。时间复杂度的最常见的表示方法为「大O表示法」,定义为:
若存在函数f(n),使得当问题规模n趋近于正无穷时,g(n)/f(n)始终小于等于某常数c,则称函数g(n)的渐进时间复杂度为O(f(n)),O(f(n))为g(n)的复杂度上界。
同理,还有其他的复杂度关系Ω(下界), Θ(精确渐近),o(松上界),ω(松下界)。
一些规定
- 复杂度的乘数可以省略:O(14n^2)应直接写为O(n^2)。
- 指数型复杂度永远大于多项式复杂度:O(3^n) > O(n^2)。
- 多项式复杂度永远大于对数复杂度:O(n) > O((logn)^3)。
二、分治算法
什么是分治算法?
字面意思是“分而治之”,就是把一个复杂的问题分成多个相同或相似的子问题,再把子问题分成更小的子问题直到最后子问题无需再分。原问题的解由子问题的解的合并而来。
基本解决步骤
- 分:将原问题分解为多个相互独立,与原问题形式相同的子问题
- 解:递归地解决各个子问题,若分支到达base case则直接解决。
- 合:将各个子问题的解合并
复杂度分析:主定理
由于分治算法的相似性,我们可以将其递归关系表示为:
\[T(n) = aT(\frac{n}{b}) + f(n)\]其中,a表示每个问题可以分解出的子问题的数量,每个子问题的规模是n/b。f(n)用来表示每个子问题中创建子问题和合并它们的结果消耗的时间。对此,主定理规定T(n)的复杂度为:
关于主定理的推导,直观上可以使用画递归树来分层求出复杂度并加和,如下图所示:
常见的递归算法及其复杂度:
经典问题:汉诺塔
有A,B,C三根柱子,将A柱上N个从小到大叠放的盘子移动到C柱,一次只能移动一个,小盘子必须在大盘子上面。求总的移动次数是多少?
如果只移动一个盘子从A到C,那我们只需要直接从A移到C即可。对于其他问题,每次移动我们都可以当做以下流程:
- 把当前盘子上方的所有盘子移到B柱。
- 把当前盘子从A柱移动到C柱。
- 把B柱上的盘子移动到C柱。
而实际上,把B柱上的盘子移动到C柱又可以理解为一个全新的问题,其中中间辅助移动的柱子是A。由此分解下去,我们终究会到达递归的基本情况,即:移动一个盘子。由此,我们给出以下代码:
hanoi(n, x, y, z) {
if (n >= 1) {
// 将n-1个盘子经由y放到z
TOH((n-1), x, z, y)
// 将第n个盘子放到y
move:x-->y
// 将n-1个盘子从z移动回来
TOH((n-1), z, y, x)
}
}