一、 数据结构

1、 红黑树、序统计树、区间树

1) 红黑树的性质、操作及时间

2) 红黑树的应用——序统计树、区间树的定义、构造

3) 数据结构的扩张步骤

1.1红黑树

红黑树的性质（P163）：(背)

1、每个结点要么是红的要么是黑的。

2、根结点是黑的。

3、每个叶结点（叶结点即指 NIL 或 NULL 结点）都是黑的。

4、如果一个结点是红的，那么它的两个儿子都是黑的。

5、 对于任意结点而言，其到叶结点树尾端 NIL 指针的每条路径都包含相同数目的黑结点。

红黑树的操作：（包括左旋、右旋 P165、查找、插入、删除，其中插入删除太复杂，不作要求）

红黑树的操作时间：

因为一棵由 n 个结点随机构造的二叉查找树的高度为 lgn，所以顺理成章，二叉查找树的一般操作的执行时间为 O(lgn)。但二叉查找树若退化成了一棵具有 n 个结点的线性链后，则这些操作最坏情况运行时间为 O(n)。

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

红黑树的应用：顺序统计树和区间树，实际都是对红黑树的扩张。

1.2动态序统计-顺序统计树

序统计：在一系列数中找出最大、最小值、某个数的序值等操作。

顺序统计树（P181）：

在包含 n 个元素的无序集合中，寻找第i个顺序统计量(关键字的值第i小)的时间复杂度为 O(n)。通过建立一种特定的结构，可以使得任意的顺序统计量都可以在 O(lgn)的时间内找到。这就是下面会提到的基于红黑树的顺序统计树。

相比于基础的数据结构，顺序统计树增加了一个域 size[x]。这个域包含以 x 为根的子树的节点数(包含 x 本身)。size 域满足等式：

size[x] = size[left[x]] + size[right[x]] + 1

顺序统计树如下图所示：

加序值是一种全局的方式，加size域是一种局部的方式，所以前者不行。

再根据红黑树的排序特性，我们就可以 O(lgn)的时间内完成下面的操作。

查找第 i 小的元素

实现 OS-SELECT(x, i)返回以 x 为根的子树中包含第 i 小关键字的节点的指针。根据排序树的性质，我们知道左子树的键值要小于根节点的键值，右节点的键值要大于根节点，这相当于静态的顺序统计量的 PARTITION 已经完成。同时我们知道左右子树的大小，我们就可以确定在哪个分支进行接下来的查找。

OS-SELECT(x, i) 整个过程如下：

每次调用，必定会下降一层，故 OS-SELECT 的时间复杂度为 O(lgn).

1.3红黑树的应用-区间树

仍然是查找问题，不同于前面的，前面的是针对单个关键字的查找问题，区间树是针对一个范围的查找问题，是比较常见的。比如过去5年硕士研究生的招生人数。

区间树是在红黑树基础上进行扩展得到的支持以区间为元素的动态集合的操作，其中每个节点的关键值是区间的左端点。通过建立这种特定的结构，可是使区间的元素的查找和插入都可以在 O(lgn)的时间内完成。

相比于基础的数据结构，增加了一个 max[x]，即以 x 为根的子树中所有区间的断点的最大值。

区间树如下图所示：

区间查找

实现 INTERVAL-SEARCH(T, i)，返回一个和区间 i 重叠的区间，若无，则返回nil[T]。

基本思想是我们通过左子树的 max 进行划分：如果左子树的 max 值小于 low[i]（左子树最大值比你区间最小值还要小，去右边找），则左子树不存在这样的区间和 i 重叠，转到右子树；否则，转到右子树，因为左子树的端点小于右子树，若左子树无可能，右子树也必然不可能。

INTERVAL-SEARCH(T, i)整个过程如下：

1.4数据结构的扩张步骤(背)

1.选择一种基础数据结构

2.确定要在基础数据结构中添加哪些信息

3.验证可用基础数据结构上的基本修改操作来维护这些新添加的信息

4.根据需求设计新的操作

2、 二项堆

1) 二项树的定义、性质

2) 二项堆的定义

3) 根表的性质

4) 二项堆的操作、时间

3、 Fib堆

1) Fib堆的定义

2) 根表的性质

3) Fib堆的操作、时间

二、算法设计方法

1、 分治法(背)

1) 基本步骤

2) 适用条件

3) 相关算法

真题1：简述分治法的适用条件。(2011)

分治法：对于一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n 较小）则直接 解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同， 递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

基本步骤： step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

适用条件：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

相关算法：

二路归并排序：

快速排序：

2、 动态规划

1) 基本步骤

2) 基本要素

3) 相关算法

1.什么是动态规划方法？

解决多阶段决策最优化的过程称为动态规划方法.

和分治法一样，动态规划是通过组合子问题的解而解决整个问题的。

与分治法不同，动态规划适用于子问题不是独立的情况，也就是子问题包含公共的子问题。

动态规划算法对每个子问题只求解一次，将其保存在一张表(二维数组)中，从而避免每次遇到各个子问题时重新计算，本质上是空间换时间。

适用于最优化问题。

2.动态规划的基本步骤？

• 描述最优解的结构的特征。（一个问题的最优解(装配线调度问题-找出通过装配站Si,j的最快路线）包含子问题(找出通过S1,j-1或S2,j-1的最快路线)的解都是最优的，这个性质称为最优子结构性质）

  eg:

• 递归定义最优解的值

• 按自底向上的方式计算出最优值

• 由计算出的结果，构造一个最优解

3.动态规划的要素

1. 所解问题必须具备最优子结构性质

   对于一个问题，怎样发现最优子结构性质？
   1.检查问题的解所面临的选择(问题的解可以是做一个选择)
   2.假定对一个给定的问题，已知某个选择导致最优解（不必关心如何确定这个旋转，尽管假定他是已知的）
   3.分析这种选择将产生多少子问题，以及如何描述所得到的的子问题空间
   4.证明子问题的解也是最优的
   eg:最长回文子串中
   1.选一个最长的回文串
   2.假设最长的长度为n时，是回文串
   3.2个子问题：去掉头或者尾。去掉一个肯定不是了，得去掉2个，去掉头尾也是回文子串。

   如第4步举例：

   

   

2. 重叠子问题

   • 虽然问题分解后是否存在重叠子问题不是应用动态规划方法的必要前提，但存在重叠子问题应用动态规划方法能提高算法效率

3. 记忆法

   • 记忆法是动态规划方法的一种变种形式，它采用自顶向下计算最优解的值

4.相关算法/问题：

• 背包问题
• 最长回文子串(leetcode)
• 最优二叉树

3、 贪心法

1) 基本思想

2) 基本要素

3) 相关算法

4) 理论基础——胚的定义及相关概念

5) 三种方法的相同及不同点

贪心算法概念：

​ 贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

贪心算法适用的问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

与动态规划算法相同的是，都具有最优子结构性质（相同点）；不同的是，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题（不同点）

基本思想：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

基本要素：

贪心选择性质：

• 所谓选择性质是指所求问题的最优解可以通过一系列局部最优的贪心选择而得到。
• 是应用贪心法求解的一个必要条件。
• 是区别动态规划方法的一个重要特征，因为贪心方法在做出选择时并不依赖将来的情况，只需根据当前的情况即可做出选择

最优子结构性质：

• 也是应用贪心法求解的一个必要条件。
• 局部最优 + 一系列贪心选择产生原问题的一个最优解

相关算法：

活动选择问题，部分背包问题

活动选择问题：

活动(使用资源，如教室)选择问题就是要选择出一个最大兼容活动子集.

每个活动ai有个开始时间si和结束时间fi , 且 0 <= si< fi< 无穷, 活动占据区间 左闭右开。

递归贪心算法。

装配线调度算法 Fastest_Way 的时间复杂度为O(n)___，最优二叉查找树算法 Optimal_BST 的时间复杂度为_____sitar(n^3^)_。

插入排序算法在最坏情况、平均情况和最好情况下的时间复杂度分别为 n方，n方，n

理论基础——胚的定义及相关概念：

1、胚（matroids)

def：一个胚应是满足下述条件的有序对 M=(S,I)

①S 是有穷非空集

②I 是 S 的一个非空独立子集族，使得若 B∈I 且A B，则 A∈I。满足此性质的 I 具有遗传性，即 B 独立，B 的集亦独立，其中 Φ∈I。

③若 A∈I，B∈I 且|A|<|B|，则存在一个元素 x∈B-A，使得 A∪{x} ∈I，则称 M 具有交换性。

例如：由无向图 G=(V,E)可定义 M G =(S G ,I G )，其中

①S G =E 为 G 中的边集

②I G 为 S G 的无回路边集族，即若 A∈E 则 A∈I G A 中无回路，边集 A 独立子图 G A =(V,A) 是一森林。

定理 16.5 若 G 是一无向图，则 M G =(S G ,I G )是一个胚。

2、最大独立子集

给定一个胚 M=(S,I)，对于 I 中一个独立子集 A∈I，若 S 中有一个元素 x 不属于 A，使得将 x 加入 A 后仍保持 A 的独立性，即 A∪{x}∈I，则称 x 为 A 的一个可扩张元素（extension）。

当胚中的一个独立子集 A 没有可扩张元素时，称 A 是一个最大独立子集。

定理 16.6 胚中所有最大独立子集大小相等

proof：设 A 和 B 是 M 的二个最大独立子集，且|A|<|B| 由胚的交换性可知，此时存在一个元素 x∈B-A，使得 A∪{x}∈I，这与 A 是最大独立子 集矛盾。

同理可证|B|<|A|时，所以|A|=|B|。

3. 加权胚

若对 M=(S,I)中的 S 给定一个权函数 w，使得对任意的 x∈S，有 w(x)>0，则称 M 为加权胚。S 的子集 A 的权可定义为：w(A)=∑w(x)，x∈A

4. 最优子集

使 w(A)权值达到最大的独立子集 A 称为最优子集。

例：求连通网络 G=(V,E)的最小生成树问题。

定义加权胚 M G =(S G ,I G )的权为 w’为：w’(e)=W 0 -w(e)>0，其中 e∈E，W 0 为大于 G 中任一边权值的常数

令 A 是 G 的生成树，则 w’(A)=(|V|-1)W 0 -w(A) 若 w’(A)最大则 w(A)最小，所以 A 是 G 的 MST。

三种方法的相同及不同点： 动态规划与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

贪心算法与动态规划算法相同的是，都具有最优子结构性质（相同点）；不同的是，动

态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，

以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问

题（不同点）

三、算法分析

1、 渐近符号

1) 定义

2) 三个符号间的关系

3) 一些已知量间的渐进关系

渐近记号

表示算法的渐近运行时间的记号是用定义域为自然数集N = {0,1,2,3,…}的函数来定义的。

最坏情况运行时间T（n）一般仅定义于整数的输入规模上。 （但定义域有时也能扩充到实数集或者缩小到自然数的某个受限子集上）。

Φ记号

$Φ(g(n)) = {f(n): 存在正常数c1,c2和n0,使对所有的n >= n0 , 有 0 <= c1g(n) <= f(n) <= c2g(n)}$

上面读作，对于一个函数f(n),若存在正常数c1,c2,使得当n充分大时，f(n)能被夹在c1g(n)和c2g(n)中间，则f(n)属于集合Φ(g(n)) , 因为Φ(f(n))是一个集合，可以写成 f(n) ∈ Φ(g(n)) ,表示f(n)是Φ(g(n))的元素。 不过，通常写成 f(n) = Φ(g(n)) 来表示相同的意思.(背)

: 读作 满足…的特性

O记号：用来表示上界。

(背)

2、 传统分析方法

1) 基本思想

2) 最好、最坏和平均情况下的时间复杂度分析

算法的运行时间是指在特定输入时，所执行的基本操作数（或步数）。

(基本的)传统分析方法：

1) 基本思想：算法中的1条指令1次执行的时间以及它在算法执行期间总的执行次数得到以后， 就得到这条指令总的执行时间，把每条指令的总的执行时间算出来相加，就得到了算法的运行时间，

2) 最好、最坏和平均情况下的时间复杂度分析

3、 递归算法的分析方法

1) T(n)的一般式(背)

2) 替换法

3) 递归树方法

4) Master方法(背)

4、 平摊分析方法

1) 基本思想

2) 合计法

3) 记账法

4) 势函数方法

5) 动态表分析

5、 算法正确性分析

1) 循环不变式

2) Cut and paste方法

3) 归纳法

4) 贪心选择性质