第一部分——第1章概述

想让APP和微信一样，可以流畅运行小程序？ | 体验即送大疆、华为、樱桃键盘！>>>

数据结构简介

使用数据结构的三个原因：效率、抽象、重用性
算法简介：效率、抽象、重用性
算法设计的一般方法：随机法、分治法、动态规划、贪心法、近似法

算法设计的一般方法

随机法

随机法依赖于随机数的统计特性。比如应用随机法的例子是快速排序。

分治法

分治法包含3个步骤：分解、求解、合并。一个分治法的例子是归并排序

动态规划

动态规划同分治法类似，都是将较大的问题分解为子问题最后再将结果合并。
不同之处，在动态规划中，处理问题的方式与子问题之间的关系有关。在分治法中，每一个子问题都是独立的。
因此，在分治法中可以以递归（第3章）的方式解决每一个子问题，然后将结果与其他子问题的结果合并。

贪心法

贪心法在求解问题时总能够做出在当前的最佳选择。换句话说，不是从整体最优上考虑，而仅仅是在某种意义上的局部最优解。

采用贪心法的例子是霍夫曼编码（第14章），是一个数据压缩算法。
霍夫曼编码中最重要的部分是构建一颗霍夫曼树（又称最优二叉树）。

• (1)为了构建一颗霍夫曼树，从它的叶子节点自底向上处理。将每个压缩的符号和它们在数据中出现的次数（频率）一起作为二叉树的根节点保存。
• (2)接下来，选择两颗拥有最小频率值得根节点作为左右子树节点，构造一颗新的二叉树，且保证新的二叉树根节点的频率值为左右子树节点的频率值之和。
• （3）然后重复这个步骤，知道得到唯一的一棵树，这就是最终的霍夫曼树。

霍夫曼树的根节点包含数据中符号的总数，叶子节点包含原始的符号以及它们出现的频率。
霍夫曼编码是一种贪心算法，因为每次它都会挑选出当前最合适的两棵树来合并。

近似法

近似法并不计算出最优解，相反，它只计算出“足够好”的解。通常利用近似法解决那些计算成本很高又因为其本身十分有价值而不愿放弃的问题。

推销员问题(第16章)是一个通常会用近似法去解决的问题。