算法(algorithm) 就是任何良定义的计算过程, 该过程取某个值或值的集合作为 输入 并产生某个值或值的集合作为 输出. 这样算法就是把输入转换成输出的计算步骤的一个序列
graph TD
A(输入) -->|算法| B(输出)
一个合法的输入序列称为排序问题的一个 实例(instance)
算法问题共有的两个特征
- 存在许多候选解, 但绝大多数候选解都没有解决手头的问题.
- 存在实际应用
算法与其他技术
- 先进的计算机体系结构与制造技术
- 易于使用、 直观的图形用户界面(GCU)
- 面向对象的系统
- 集成的万维网技术
- 有线与无线网络的快速组网
循环不变式性质:
- 初始化: 循环的第一次迭代之前, 它为真.
- 保持: 如果循环的某次迭代之前它为真, 那么下次迭代之前它仍为真.
- 终止: 在循环终止时, 不变式为我们提供一个有用的性质, 该性质有助于证明算法是正确的
伪代码 中的一些约定
- 缩进表示块结构
- for循环每次迭代增加其循环计数器时, 我们使用关键词 to. 当一个for循环每次迭代减少其循环计数器时, 我们使用关键词 downto
- 符号"//"表示该行后面部分是个注释
- 记号".."用于表示数组中值的一个范围
- 复合数据结构被组织成对象, 对象又由属性组成. 我们使用许多面向对象编程语言中创建的句法来访问特定的属性: 对象名后跟一个点再跟属性名
我们把表示一个数组或对象的变量看做指向表示数组或对象的数据的一个指针
有时, 一个指针根本不指向任何对象. 这是, 我们赋给它特殊值 NIL - 我们按__值__把参数传递给过程: 被调用过程接受其参数自身的副本. 如果它对某个参数赋值, 调用过程看不到这种改变
- 一个 return 语句立即将控制返回到调用过程的调用点.
我们允许在单一的 return 语句中返回多个值 - 布尔运算符"and"和"or"都是 短路的
- 关键词 error 表示因为已被调用的过程情况不对而出现了一个错误. 调用过程负责处理该错误, 所以我们不用说明将采取什么行动
我们真正感兴趣的是运行时间的 增长率 或 增长量级
分治法 的思想: 将原问题分解为几个规模较小但类似于原问题的子问题, 递归地求解这些子问题, 然后再合并这些子问题的解来建立原问题的解. 分治模式 在每层递归时都有三个步骤:
- 分解 原问题为若干子问题, 这些子问题是原问题的规模较小的实例.
- 解决 这些子问题, 递归地求解各子问题. 然而, 若子问题的规模足够小, 则直接求解
- 合并 这些子问题的解成原问题的解
可以用递归方程或递归式来描述其运行时间 假设把原问题分别成a个子问题, 每个子问题的规模是原问题的1/b. 为了求解一个规模为n/b的子问题, 需要T(n/b)的时间, 所以需要aT(n/b)的时间来求解a个子问题. 如果分解问题成子问题需要时间D(n), 合并子问题的解成原问题的解需要时间C(n). T(n) = aT(n/b) + D(n) + C(n)
对所有的n≥n0, 函数f(n)在一个常量银子内等于g(n). 我们称g(n)是f(n)的一个 渐进紧确界(asymptotically tight bound) O记号: 渐进上界 Ω记号: 渐进下界
多项式: 若对某个常量k, 有f(n)=O(n^k), 则称函数f(n)是多项式有界的 对数: 若对某个常量k, f(n)=O(lg^kn), 则称函数f(n)是多对数有界的
当子问题足够大, 需要递归求解时, 我们称之 递归情况(recursive case) 当子问题变得足够小, 不再需要递归时, 我们说递归已经"触底", 进入了 基本情况(base case)
给出一段时间的股票价格变化, 确定买入卖出时间以获得最大收益 问题转化为寻找价格变化的和的最大非空连续子数组, 最大子数组(maximum subarray):
- 完全位于左边的子数组中, low≤i≤j≤mid
- 完全位于右边的子数组中, mid≤i≤j≤high
- 求取跨越中点的最大子数组, 因此low≤i≤mid<j≤high: 从中点开始分别向两端求取有最大和的子数组 时间复杂度为O(nlgn) 最优解: 从数组的左边界开始, 由左至右处理, 记录到目前为止已经处理过的最大子数组. 若已知A[1..j]的最大子数组, 基于以下性质将解扩展为A[1..j+1]的最大子数组: A[1..j+1]要么是A[1..j]的最大子数组, 要么是某个子数组A1..j+1
我们可以不必复制元素就能完成矩阵的分解, 其中的诀窍是使用下标计算 虽然渐进符号包含了常数因子, 但递归符号(如T(n/2))并不包含
证明上界失败时, 不一定要将猜测减少, 实际上证明一个更弱的上界可能会更困难一些, 但因为为了证明一个更弱的上界, 我们在归纳证明中也必须使用同样更弱的界
在 递归树 中, 每个结点表示一个单一子问题的代价
T(n) = aT(n/b) + f(n) 其中 a ≥ 1和 b > 1是常数, f(n)是渐进正函数 主定理: 令a ≥ 1和 b > 1是常数, f(n)是一个函数, T(n)是定义在非负整数上的递归式: T(n) = aT(n/b) + f(n) 其中我们将 n / b解释为 └ n / b ┘ 或 ┌ n / b ┐. 那么 T(n)有如下渐进界:
- 若对某个常数 ε > 0有 f(n) = O(n ^ log[b][a] - ε), 则 T(n) = Θ(n ^ log[b][a]).
- 若 f(n) = Θ(n ^ log[b][a]), 则 T(n) = O(n ^ log[b][a]lgn).
- 若对某个常数 ε > 0有 f(n) = Ω(n ^ log[b][a] + ε), 且对某个常数 c < 1和所有足够大的 n有 af(n / b) ≤ cf(n). 则 T(n) = Θ(f(n))
从递归树看, 主定理的三种情况分别对应以下三种情况:
(1)树的总代价由叶结点的代价决定; (2)树的总代价均匀分布在树的所有层次上; (3)树的总代价由根结点的代价决定.
概率分析 是在问题分析中应用概率的理念. 实际上, 我们对所有可能输入产生的运行时间取平均. 当报告此种类型的运行时间时, 我们称其为 平均情况运行时间.
随机算法 如果一个算法的行为不仅由输入决定, 而且也由 随机数生成器(random-number generator) 产生的数值决定, 则称这个算法是 随机的(randomized). 我们将一个随机算法的运行时间称为 期望运行时间.
我们采用指示器随机变量(indicator random variable). 给定一个样本空间 S和一个事件 A, 那么事件 A对应的 指示器随机变量 I{A}定义为 :
I{A} = 1 -> 如果 A发生 I{A} = 0 -> 如果 A不发生
随机交换算法(RANDOMIZE-IN-PLACE)能产生一个均匀随机排列. 一个具有 n个元素的 k排列(k-permutation) 是包含这 n个元素中的 k个元素的序列, 并且不重复. 一共有 n! / (n - k)!种可能的 k排列.
Pr{B(k)} = Pr{B(k - 1)}Pr{A(k) | B(k - 1)} ... = Pr{B(1)}Pr{A(2) | B(1)}...Pr{A(k) | B(k - 1)} = 1 * (1 - 1 / n) * ... (1 - (k - 1) / n) 由 1 + x ≤ e ^ x, Pr{B(k)} ≤ e ^ (-k * (k - 1) / (2 * n)) ≤ 1 / 2 当 n = 365时, k ≥ 23
礼券收集者问题 一个人想要收集齐 b种不同礼券中的每一种, 大约需要 blnb张随机得到的礼券才能成功
抛投一枚标准的硬币 n次, 最长连续正面的序列的期望长度: Θ(lgn).
策略: 选择一个正整数 k < n, 面试然后拒绝前 k个应聘者, 再雇佣其后比前面的应聘者有更高分数的第一个应聘者. 如果最好的应聘者在前 k个面试之中, 那么将雇佣第 n个应聘者. 如果用 k = n / e来实现我们的策略, 那么将以至少 1 / e的概率成功雇佣到最好的应聘者.
在实际中, 待排序的数很少是单独的数值, 他们通常是称为 记录(record) 的数据集的一部分. 每个记录包含一个 关键字(key), 就是排序问题中要重排的值. 记录的剩余部分由 卫星数据(satellite data) 组成, 通常与关键字是一同存取的. 在关注排序问题时, 我们通常假定输入只是由数组成. 排序算法 如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外, 则称排序算法是 原址的(in place).
堆排序(heapsort)
基本过程:
- MAX-HEAPIFY 过程: 其时间复杂度为 O(lgn), 它是维护最大堆性质的关键.
- BUILD-MAX-HEAP 过程: 具有线性时间复杂度,功能是从无序的输入数据数组中构造一个最大堆.
- HEAPSORT 过程: 其时间复杂度为 O(nlgn), 功能是对一个数组进行原址排序.
- MAX-HEAP-INSERT、HEAP-EXTRACT-MAX、HEAP-INCREASE-KEY、HEAP-MAXIMUM 过程: 时间复杂度为 O(lgn), 功能是利用堆实现一个优先队列.
递归调用 MAX-HEAPIFY
对树中的所有非叶结点都调用一次 MAX-HEAPIFY 我们可以在线性时间内, 把一个无序数组构造称为一个最大堆
HEAPSORT过程的时间复杂度是 O(nlgn)
优先队列(priority queue) 是一种用来维护由一组元素构成的集合 S的数据结构, 其中的每一个元素都有一个相关的值, 称为 关键字(key). 一个 最大有限队列 支持以下操作:
INSERT(S, x): 把元素 x插入到集合 S中. 这一操作等价于 S = S ∪ {x}. MAXIMUM(S): 返回 S中具有最大键字的元素. EXTRACT-MAX(S): 去掉并返回 S中具有最大键字的元素. INCREASE-KEY(S, x, k): 将元素 x的关键字值增加到 k, 这里假设 k的值不小于 x的原关键字值
在用堆来实现有限队列时, 需要在堆中的每个元素里存储对应对象的 句柄(handle). 句柄(如一个指针或一个整型数等)的准确含义依赖于具体的应用程序.
过程 HEAP-MAXIMUM可以在 Θ(1)的时间内实现 MAXIMUM操作. 其他过程的时间复杂度为 O(lgn)
选择一个 x = A[r]作为 主元(pivot element), 并围绕它来划分子数组 A[p..r], 原址重排.
最坏情况划分: T(n) = T(n - 1) + Θ(n) 最好情况划分: T(n) = 2T(n / 2) + Θ(n) 平衡的划分: 事实上, 任何一种常数比例的划分都会产生深度为 Θ(lgn)的递归树, 其中每一层的时间代价都是 O(n). 因此, 只要划分是常数比例的, 算法的运行时间总是 O(nlgn). 对于平均情况的直观观察: 从直观上看, 差划分的代价 Θ(n - 1)可以被吸收到好划分的代价 Θ(n)中取, 而得到的划分结果也是好的. 因此, 当好和差的划分交替出现时, 快速排序的时间复杂度与全是好的划分时一样, 仍然是 O(nlgn). 区别只是 O符号中隐含的常数因子要略大一些.
随机抽样(random sampling) 的随机化技术, 可以使得分析变得更加简单. 与始终采用 A[r]作为主元的方法不同, 随机抽样是从子数组 A[p..r]中随机选择一个元素作为主元.
在输入元素互异的情况下, 快读排序算法的期望运行时间为 O(nlgn).
在排序的最终结果中, 各元素的次序依赖于他们之间的比较. 我们把这类排序算法称为 比较排序. 任何比较排序在最坏情况下都要经过 Ω(nlgn)次比较.
决策树模型 比较排序可以被抽象为一棵决策树. 决策树 是一棵完全二叉树, 它可以表示在给定输入规模情况下, 某一特定排序算法对所有元素的比较操作. 一棵高度为 h、具有l个可达叶结点的决策树, 它对应一个对 n个元素所做的比较排序. n! ≤ l ≤ 2 ^ h 取对数 h ≥ lg(n!) = Ω(nlgn)
计数排序 假设 n个输入元素中的每一个都是在 0到 k区间内的一个整数, 其中 k为某个整数. 当 k = O(n)时, 排序的运行时间为 Θ(n). 计数排序的一个重要性质就是它是 稳定的
基数排序(radix sort) 是一种用在卡片排序机上的算法. 给定 n个 d位数, 其中每一个数位都有 k个可能的取值. 如果 RADIX-SORT使用的稳定排序方法耗时 Θ(n + k), 那么它就可以在 Θ(d(n + k))时间内将这些数排好序 给定 n个 b位数和任何正整数 r ≤ b, 如果 RADIX-SORT 使用的稳定排序算法对数据取值区间是 0到 k的输入进行排序耗时 Θ(n + k), 那么它就可以在 Θ((b / r)(n + 2 ^ r))时间内将这些数排好序 快速排序通常可以比基数排序更有效地使用硬件的缓存
桶排序(bucket sort) 假设输入数据服从均匀分布, 平均情况下它的时间代价为 O(n). 桶排序假设输入是由一个随机过程产生, 该过程将元素均匀、独立地分布在 [0, 1)区间上. 桶排序将 [0, 1)区间划分为 n个相同大小的子区间, 或称为 桶. 所有桶的大小的平方和与总的元素数呈线性关系, 那么桶排序仍然能在线性时间完成.
第 i个 顺序统计量(order statistic) 是该集合中的第 i小的元素, 最小值是第 1个顺序统计量(i = 1), 最大值是第 n个顺序统计量(i = n). 用非形式化的描述来说, 一个 中位数(median) 是它所属集合的"中点元素".
只需要最多 3└n / 2┘次比较就可以同时找到最小值和最大值.
采用快速排序的一部分, 称 A[q]为 主元(pivot). 假设所有元素是互异的, 在期望线性时间内, 我们可以找到任一顺序统计量, 特别是中位数.
算法可以确定一个有 n > 1个不同元素的输入数组中第 i小的元素. (如果 n = 1, 则算法值返回唯一输入数值作为第 i小的元素)
支持在集合中插入和删除元素, 以及测试元素是否属于集合这些操作的动态集合称为 字典(dictionary) 一些类型的动态集合假定对象中的一个属性为标识 关键字(key). 如果关键字全不相同, 可以将动态集合视为一个关键字值的集合. 对象可能包含 卫星数据.
在 栈(stack) 中, 被删除的是最近插入的元素: 栈实现的时一种 后进先出(last-in, first-out, LIFO) 策略. 类似地, 在 队列(queue) 中, 被删去的总是在集合中存在时间最长的那个元素: 队列实现的是一种 先进先出(first-in, first-out, FIFO) 策略.
链表(linked list) 是这样的数据结构, 其中的各对象按线性顺序排列. 链表的顺序是由各个对象里的指针决定的. 哨兵(sentinel) 是一个哑对象, 其作用是简化边界条件的处理. 将一个常规的双向链表转变为一个 有哨兵的双向循环链表(circular, doubly linked list with a sentinel), 哨兵 L.nil位于表头和表尾之间. 属性 L.nil.next指向表头, L.nil.prev指向表尾.
对每个属性使用一个数组表示, 可以赖表示一组有相同属性的对象.
单数组的表示法比较灵活, 因为它允许不同长度的对象存储于同一数组中.
有必要对链表表示中尚未利用的对象空间进行管理, 使其能被分配. 垃圾收集器(garbage collector) 负责确定哪些对象是未使用的. 余下的 m - n个对象是 自由的(free) 我们把自由对象保存在一个单链表中, 称为 自由表(free list).
左孩子右兄弟表示法(left-child, right-sibling representation)
散列表(hash table) 是实现字典操作的一种有效数据结构
用一个数组, 或称为 直接寻址表(direct-address table), 记为 T[0..m - 1], 其中每个位置, 或称为 槽(slot), 对应全域 U中的一个关键字.
在散列方式下, 该元素存放在槽 h(k)中; 即利用 散列函数(hash function) h, 由关键字 k计算出槽的位置. 可以说一个具有关键字 k的元素被 散列 到槽 h(k)上, 也可以说 h(k)是关键字 k的 散列值.
这里存在一个问题: 两个关键字可能映射到同一个槽中, 我们称这种情形为 冲突(collision).
用链表存放散列值相同的关键字
给定一个能存放 n个元素的、具有 m个槽位的散列表 T, 定义 T的 装在因子(load factor) α为 n / m, 即一个链的平均存储元素数. 假定任何一个给定元素等可能地散列到 m个槽中的任何一个, 且与其他元素被散列到什么位置上无关. 称这个假设为 简单均匀散列(simple uniform hashing).
唯一有效的改进方法是随机地选择散列函数, 使之独立与要存储的关键字. 这种方法称为 全域散列(universal hashing).
在 开放寻址法(open addressing) 中, 所有的元素都存放在散列表里. 为了使用开放寻址法插入一个元素, 需要连续地检查散列表, 或称为 探查(probe), 直到找到一个空槽来放置待插入的关键字为止. 对每一个关键字 k, 使用开放寻址法的 探查序列(probe sequence) <h(k, 0), h(k, 1), ..., h(k, m - 1)>是 <0, 1, ..., m - 1>的一个排列.
给定一个普通的散列函数 h': U -> {0, 1, ..., m - 1}, 称之为 辅助散列函数(auxiliary hash function), 线性探查(linear probing) 方法采用的散列函数为: h(k, i) = (h'(k) + i) mod m, i = 0, 1, ..., m - 1 存在一个问题, 称为 一次群集(primary clustering)
二次探查(quadratic probing) 采用如下形式的散列函数: h(k, i) = (h'(k) + c1i + c2i ^ 2) mod m, c1, c2 > 0, 这一性质可导致一种轻度的群集, 称为 二次群集(secondary clustering)
双重排列(double hashing) 是用于开放寻址法的最好方法之一: h(k, i) = (h1(k) + ih2(k)) mod m
给定一个装载因子为 α = n / m < 1的开放寻址散列表, 并假设是均匀散列的, 则对于一次不成功的查找, 其期望的探查次数至多为 1 / (1 - α). 一次成功查找中的探查期望至多为: (1 / α)ln (1 / (1 - α)) 如果散列表是半满的, 则一次成功的查找中, 探查的期望数小于 1.387. 如果散列表为 90%满的, 则探查的期望数小于 2.559.
完全散列(perfect hashing), 用该方法进行查找时, 能在最坏情况下用 O(1)次访存. 如果从一个全域散列函数类中随机选出散列函数 h, 将 n个关键字存储在一个大小为 m = n ^ 2的散列表中, 那么表中出现冲突的概率小于 1 / 2. 如果从一个全域散列函数类中随机选出散列函数 h, 用它将 n个关键字存储到大小为 m = n的散列表中, 则有 E[Σn ^ 2j(j = 0 -> m - 1)] < 2 * n, 这里 nj为散列到槽 j中的关键字数.
对任何结点 x, 其左子树中的关键字最大不超过 x.key, 其右子树中的关键字最小不低于 x.key. 中序遍历(inorder tree walk) 按序输出二叉搜索树的所有关键字. 先序遍历(preorder tree walk) 中输出的根的关键字在其左右子树的关键字值之前. 后序遍历(postorder tree walk) 输出的根的关键字在其左右子树的关键字值之后.
在一棵高度为 h的二叉搜索树上, 动态集合上的操作 SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和 PREDECESSOR可以在 O(h)时间内完成.
在一棵高度为 h的二叉搜索树上, 实现动态集合上的操作 INSERT和 DELETE的运行时间均为 O(h).
定义 指数高度(exponential height) Yn = 2 ^ Xn, 设 Rn为一个随机变量, 表示这个关键字在 n个关键字集合中的 秩(rank). E[Xn] = O(lgn)
红黑树(red-black tree) 是一棵二叉搜索树, 它在每个结点上增加了一个存储位来表示结点的 颜色 可以是 RED或 BLACK. 红黑树确保没有一条路径会比其他路径长出 2倍, 因而是近似于 平衡的.
红黑性质:
- 每个结点或是黑色的, 或是红色的.
- 根结点是黑色的.
- 每个叶结点(NIL)是黑色的.
- 如果一个结点是红色的, 则它的两个子结点都是黑色的.
- 对每个结点, 从该结点到其所有后代叶结点的简单路径上, 均包含相同数目的黑色结点. 从某个结点 x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的 黑高(black-height), 记为bh(k). 一棵有 n个内部结点的红黑树的高度至多为 2lg(n + 1).
指针结构的修改是通过 旋转(rotation) 来完成的, 这是一种能保持二叉搜索树性质的搜索树局部操作. LEFT-ROTATE和 RIGHT-ROTATE都在 O(1)时间内运行完成.
将结点z插入, 然后着为红色: 性质1和性质3继续成立, 因为新插入的红结点的两个子结点都是哨兵 T.nil. 性质5, 即从一个指定结点开始的每条简单路径上的黑结点的个数都是相等的, 也会成立, 因为结点 z代替了(黑色)哨兵, 并且结点 z本身是有哨兵孩子的红结点. 这样来看, 仅可能被破坏的就是性质2和性质4, 即根结点需要为黑色以及一个红结点不能有红孩子. 情况1: z的叔结点 y是红色的 情况2: z的叔结点 y是黑色的且 z是一个右孩子 情况3: z的叔结点 y是黑色的且 z是一个左孩子 RB-INSERT 总共花费 O(lgn)时间, 此外, 该程序所做的旋转从不超过 2次.
- 始终维持结点 y为从树中删除的结点或者移至树内的结点.
- 由于结点 y的颜色可能改变, 变量 y-original-color 存储了发生改变前的 y颜色.
- 保存结点 x的踪迹, 使它移至结点 y的原始位置上.
- 因为结点 x移动到结点 y的原始位置, 属性 x.p总是被设置指向树中 y父结点的原始位置, 甚至当 x是哨兵 T.nil时也是这样.
- 最后, 如果结点 y是黑色, 就有可能已经引入了一个或多个红黑性质被破坏的情况, 调用 RB-DELETE-FIXUP来恢复红黑性质
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.RIGHT
RB-TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
x = z.LEFT
RB-TRANSPLANT(T, z, z.left)
else y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y
else RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)
RB-TRANSPLANT(T, u, v)
if u.p == T.nil
T.root = v
elseif u == u.p.left
u.p.left = v
else u.p.right = v
v.p = u.p
RB-DELETE-FIXUP(T, x)
while x != T.root and x.color == BLACK
if x == x.p.left
w = x.p.right
if w.color == RED
w.color = BLACK
x.p.color = RED
LEFT-ROTATE(T, x.p)
w = x.p.right
if w.left.color == BLACK and w.right.color == BLACK
w.color = RED
x = x.p
elseif w.right.color == BLACK
w.left.color = BLACK
w.color = RED
RIGHT-ROTATE(T, w)
w = x.p.right
w.color = x.p.color
x.p.color = BLACK
w.right.color = BLACK
LEFT-ROTATE(T, x.p)
x = T.root
else (same as then clause with "right" and "left" exchanged)
x.color = BLACK
如果结点 y是黑色的, 这会产生三个问题:
- 如果 y是原来的根结点, 而 y的一个红色的孩子成为新的根结点, 这就违反了性质2
- 如果 x和 x.p是红色的, 则违反了性质4
- 在树中移动 y将导致先前包含 y的任何简单路径上黑结点个数少1, 因此 y的任何祖先都不满足性质5 过程 RB-DELETE-FIXUP恢复性质1、性质2和性质4. while循环的目标是将额外的黑色沿树上移. 在 while循环中, x总是指向一个具有双重黑色的非根结点. 情况1: x的兄弟结点 w是红色的 情况2: x的兄弟结点 w是黑色的, 而且 w的两个子节点都是黑色的 情况3: x的兄弟结点 w是黑色的, w的左孩子是红色的, w的右孩子是黑色的 情况4: x的兄弟结点 w是黑色的, 且 w的右孩子是红色的 运行总时间为 O(lgn)
修改红黑树, 使得可以在 O(lgn)时间内确定任何的顺序统计量. 如何在 O(lgn)时间内计算一个元素的 秩, 即它在集合线性序中的位置. 顺序统计树(order-statistic tree) T值是简单地在每个结点上存储附加信息的一棵红黑树. x.size = x.left.size + x.right.size + 1 我们通过定义一个元素的秩为在中序遍历树时输出的位置, 来消除原顺序统计树定义的不确定性.
- 选择一种基础数据结构.
- 确定基础数据结构中要维护的附加信息.
- 检验基础数据结构上的基本修改操作是否维护附加信息.
- 设计一些新操作.
闭区间(closed interval) 是一个实数的有序对 [t1, t2], 其中 t1 ≤ t2. 开(open) 区间和 半开(half-open) 区间分别略去了集合的两个或一个端点. 可以把一个区间 [t1, t2]表示成一个对象 i, 其中属性 i.low = t1为 低端点(low endpoint), 属性 i.high为 高端点(high endpoint). 我们称区间 i和 i' 重叠(overlap), 如果 i ∩ i' ≠ ∅, 即如果 i.low ≤ i'.high且 i'.low ≤ i.gigh.
区间树(interval tree) 是一种对动态集合进行维护的红黑树.
动态规划(dynamic programming) 与分治方法相似, 都是通过组合子问题的解来求解原问题(在这里, "programming"指的是一种表格法, 并非编写计算机程序) 动态规划方法通常用来求解 最优化问题(optimization problem). 我们称这样的解为问题的 一个最优解(an optimal solution), 而不是 最优解(the optimal solution), 因为可能有多个解都达到最优值.
- 刻画一个最优解的结构特征.
- 递归地定义最优解的值.
- 计算最优解的值, 通常采用自底向上的方法.
- 利用计算出的信息构造一个最优解.
最优子结构(optimal substructure) 性质: 问题的最优解由相关子问题的最优解组合而成, 而这些子问题可以独立求解.
动态规划方法仔细安排求解顺序, 对每个子问题只求解一个, 并将结果保存下来. 动态规划方法是付出额外的内存空间来节省计算时间, 是典型的时空权衡(time-memory-trade-off)的例子.
第一种方法称为 带备忘的自顶向下法(top-down with memoization) 递归过程是 带备忘的(memoized) 第二种方法称为 自底向上法(bottom-up method) 自顶向下方法并未真正递归地考察所有可能的子问题. 由于没有频繁的递归函数调用的开销, 自底向上方法的时间复杂性函数通常具有更小的系数.
时间复杂度 O(2 ^ n) -> O(n ^ 2) 空间复杂度 O(1) -> O(n)
自底向上动态规划算法是按"逆拓扑序"(reverse topological sort)或"反序的拓扑序"(topological sort of the transpose)来处理子问题图中的顶点.
有如下性质的矩阵乘积链为 完全括号化的(fully parenthesized): 它是单一矩阵, 或者是两个完全括号化的矩阵乘积链的积, 且已外加括号. 两个矩阵 A和 B只有 相容(compatible), 即 A的列数等于 B的行数时, 才能相乘.
矩阵链乘法问题(matrix-chain multiplication problem) 可描述如下: 给定 n个矩阵的链 <A1, A2, ..., An>, 矩阵 A1的规模为 p(i - 1) × p(i)(1 ≤ i ≤ n), 求完全括号化方案, 使得计算乘积 A1A2...An所需标量乘法次数最少.
一个相似的递归公式产生的序列为 卡塔兰数(Catalan numbers), 这个序列的增长速度为 Ω(4 ^ n / n ^ 3 / 2).
子问题重叠的性质是应用动态规划的另一个表示(第一个标识是最优子结构).
时间复杂度 O(2 ^ n) -> O(n ^ 2) 空间复杂度 O(n) -> O(n ^ 2)
如果一个问题的最优解包含其子问题的最优解, 我们就称此问题具有最优子结构性质.
- 证明问题最优解的第一个组成部分是做出一个选择, 做出这次选择会产生一个或多个待解的子问题.
- 对于一个给定问题, 在其可能的第一步选择中, 你假定已经知道那种选择才会得到最优解. 你现在并不关心这种选择具体是如何得到的, 只是假定已经知道了这种选择.
- 给定可获得最优解的选择后, 你确定这次选择会产生那些子问题, 以及如何最好地刻画子问题空间.
- 利用"剪切-粘贴"(cut-and-paste)技术证明: 作为构成原问题最优解的组成部分, 每个子问题的解就是它本身的最优解.
最优子结构的不同体现在两个方面:
- 原问题的最优解中涉及多少个子问题, 以及
- 在确定最优解使用那些子问题时, 我们需要考察多少种选择.
原问题最优解的代价通常就是子问题最优解的代价再加上由此次选择直接产生的代价.
无权(unweighted)最短路径: 找到一条从 u到 v的边数最少的路径. 无权最长路径: 找到一条从 u到 v的边数最多的简单路径. 两个最短路径子问题是 无关的(independent). 子问题无关的含义是, 同一个原问题的一个子问题的解不影响另一个子问题的解.
如果递归算法反复求解相同的子问题, 我们就称最优化问题具有 重叠子问题(overlapping subproblems) 性质.
构造一棵期望搜索代价最小的二叉搜索树
- 将最优化问题转化为这样的形式: 对其做出一次选择后, 只剩下一个子问题需要求解.
- 证明做出贪心选择后, 原问题总是存在最优解, 即贪心选择总是安全的.
- 证明做出贪心选择后, 剩余的子问题满足性质: 其最优解与贪心选择组合即可得到原问题的最优解, 这样就得到了最优子结构.
第一个关键要素是 贪心选择性质(greedy-choice property): 我们可以通过做出局部最优(贪心)选择来构造全局最优解.
如果一个问题的最优解包含其子问题的最优解, 则称此问题具有 最优子结构 性质. 此性质是能否应用动态规划和贪心方法的关键要素.
0-1背包问题(0-1 knapsack problem): 动态规划 分数背包问题(fractional knapsack problem): 贪心
变长编码(variable-length code) 前缀码(prefix code) 文件的最优编码方案总是对应一个满(full)二叉树, 即每个非叶结点都有两个孩子结点