算法学习笔记(一)

本篇博文对常见算法进行总结和整理,内容安排遵照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(松上界),ω(松下界)。

一些规定

  1. 复杂度的乘数可以省略:O(14n^2)应直接写为O(n^2)。
  2. 指数型复杂度永远大于多项式复杂度:O(3^n) > O(n^2)。
  3. 多项式复杂度永远大于对数复杂度: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)    
    } 
}