《算法之道》精华 算法设计部分

• 本书作者绉恒明，作者另有一本书《数据结构之弦》，以及《操作系统之哲学原理》都是很好的书
• 这本书可以算得上是深入浅出，文笔很好，作者添加了很多自己的思考
• 本文仅包括算法设计部分，算法分析略去，并没有严格按照章节顺序来记录

附录 算法随想

• 有人喜欢遍历，希望踏遍千山万水，人生丰富多彩；有人一生贪婪，眼界不宽，及时行乐；有人注定穷搜，辛辛苦苦，收获有限；有人善用时空均衡，用最少的时间办最多的事情，十分精明；有人会分治，再难的问题也能解决；有人动态规划，积少成多

第三章 分治与递归

• 生活中的例子：天平秤球以辨明次品；乘法运算；世界杯晋级赛；秦国合纵连横
• 分治策略步骤：1，将问题分为若干小问题；2，递归解决这些子问题；3，合并子问题的解答，得到大问题的解
• 标准分治策略的定义里面包含递归：T(n) = aT(n/b) + f(n)
• 递归式复杂度大师解法：

  T(n) 
  = aT(n/b) + f(n) 
  = a^2T(n/b^2) + af(n/b) + f(n)
  = a^(log_b(n)) T(1) + a^(log_b(n-1) f(n/b^(log_b(n-1))) +...+a^2f(n/b^2) + af(n/b) + f(n)
  = O(n^log_b(a)) + sum(a^j f(n/b^j))|(j = 0...log_b(n-1))

• 前项为递归树最后一层节点数，后项为递归树各层分治过程分解与合并的代价
• f(n) < n^log_b(a)时，T(n) = O(n^log_b(a))
• f(n) > n^log_b(a) : T(n) = O(f(n))
• 算法题中常见分治例子：乘方运算、矩阵乘法、斐波那契数列的矩阵乘方解法、VLSI布线

第四章 动态规划

• 动态规划是一种更有针对性的分治，分解得到的小问题很多重复，保存已经计算得到的结果可以免去重复计算
• 动态规划每一步做出一个最优选择，该最优选择与子问题的最优解组合得到大问题的最优解
• 具体步骤：
  1. 证明问题的解决方案中包括一个选择，选择后剩下一个或多个子问题
  2. 设计递归描述方式，得到递归方程
  3. 证明对大问题的最优解包括对所有子问题的最优解
  4. 证明子问题之间重叠
• 两个原则：最优子结构，重叠子问题
• 动态规划的时间复杂度：全部子问题数量x选择成本
• 算法题中常见动态规划例子：最长公共子序列（最长递增、最长递减子序列，编辑距离）、最优二叉搜索树

第五章 贪婪选择思想

• 动态规划在做出选择之前，将所有选择的结果做了比较，而如果选择的时候不经过比较，而是直接选择局部最优，就是贪婪
• 贪婪的目的只是找出一种可行解，在一定情况下找出的是最优解
• 贪婪与动态规划相同，都是一种分治策略。但与动态规划不同，贪婪将大问题分解为一个，而不是多个子问题
• 具体步骤：
  1. 将原问题表述为一个做出一个选择，然后剩下唯一一个子问题的形式
  2. 证明所有的最优选择里面总有一个是贪婪选择
  3. 证明贪婪选择加上对剩下子问题的最优解导致大问题的最优解
• 贪婪的两个原则：最优子结构（大问题的最优解包括小问题的最优解），贪婪选择属性
• 贪婪选择属性：每个小问题可以贪婪选择获得
• 算法题中常见贪婪例子：
  • 背包问题：财宝是否可以分割、每件财宝是否可以重复拿四个版本
  • 教室课程规划
  • 最小生成树
    • Kruskal算法，每次加入一个不形成环的最小的边，复杂度为O(E log(V))
    • Prime算法：每次加入距离最近的点，并降距，复杂度为O(V^2)，采用堆实现，可以达到O(E log(V))
  • 霍夫曼编码

第六章 随机化思想

• 蒙特卡洛算法：大概率输出正确答案，复杂度固定
• 常见随机化算法例子：
  • 素性测试：根据费马小定理，若p为素数，则(a^p - a) % p == 0；如果测试一百次都成立，则为合数的概率只有2^(-100)
  • 矩阵乘积结果验证：取随机二进制01矢量z，有zAB = z(AB)
  • 线性时间最小生成树算法