非形式地说，算法就是任何良定义(well-defined)的计算过程，该过程取某个值或值的集合作为输入(input)，并产生某个值或者值的集合作为输出(output)。
算法是一组有穷的规则，它规定了解决某一特定类型问题 的一系列运算
算法的五个重要特性:确定性、能行性、输入、输出、有穷性
为什么我们更关心算法的最坏情况执行时间:一个算法的最坏情况执行时间给出了任何输入的运行时间的一个 上界。知道了这个界，就能确保算法绝不需要更长的时间，我们就不需要再对算法做更坏的打算。
* 对某些算法，最坏情况经常出现。
* 对很多算法，平均情况往往与最坏情况大致一样
循环过程具有以下性质:子数组A[1~j-1]是已经被排好序的子序列。 这一性质，在j被赋予初值2，首次进入循环之前成立，而且每次循环之后(j加了1)、进入下一次循环之前也成立。
* 在第一次进入循环之前成立、每次循环之后还 成立的关系称为“循环不变式”或“循环不变性质”
(初始化、保持、终止)
O:上界函数--f(n)=Ο(g(n))表示如果算法用n值不变的同一类数据(规模 相等，性质相同)在某台机器上运行，所用的时间总小于 |g(n)|的一个常数倍。
Ω:下界函数--f(n)=Ω(g(n))表示如果算法用n值不变的同一类数据在某台 机器上运行，所用的时间总不小于|g(n)|的一个常数倍。
Θ:渐近紧确界函数--既有 f(n) = Ω(g(n))，又有f(n) = Ο(g(n))
o:非渐近紧确界上界--对任意正常数c，存在常数n0>0，使对所有的n≥n0，有|f(n)| ≤ c|g(n)|，则记作:f(n) = o(g(n))。
ω:非渐近紧确界下界--对任意正常数c，存在常数n0>0，使对所有的n≥n0， 有c|g(n)|≤|f(n)| ，则记作:f(n) = ω(g(n))。
分冶:当问题规模比较大而无法直接求解时，将原始问题分解为几个规模较小、性质与原始问题一样的子问题，然后递归地求解这些子问题，最后合并子问题的解以得到原始问题的解。(分解--解决--合并)ep:归并排序4.1(最大子数组问题)重点
我们需要一个辅助数组sum，其中sum[i]为以a[i]为尾元素的最大子数列【精髓】，待sum数组全部完成后，找出sum数组里元素的最大值，即为答案。
动态转移方程：sum[i+1] = max(sum[i]+a[i+1], a[i+1])4.3(求解递归式)熟悉
1⃣️代换法:先猜测解的形式,再用数学归纳法证明
2⃣️递归树法反应递归的执行过程。每个节点表示一个单一子问题的代价，子问题对应某次递归调用。根节点代表顶层调用的代价,子节点分别代表各层递归调用的代价。:T (n)=3T (n / 4) = cn2
3⃣️主方法:T(n) = aT(n/b)+f(n)4.4(用递归树法求解递归式)熟悉
期望运行时间:我们将一个随机算法的平均运行时间称为期望运行时间
当概率分布是发生在算法的原始输入上时，我们讨论算法的“平均情况运行时间”，而当算法本身做出随机 选择时，我们讨论算法的“期望运行时间”。在最坏情况下,任何比较排序算法都需要做Ω(nlogn)次比较
推论:堆排序和归并排序都是渐近最优的比较排序算法选择算法是一种在列表或数组中找到第k个最小数字的算法
PARTITION(1,n):设在第一次划分后，主元素v被放在位置 A(j)上，则有j-1个元素小于或等于A(j)，
且有n-j个元素大于或等于A(j).
- 若i=j，则A(j)即是第i小元素;否则，
- 若i<j，则A(1:n)中的第i小元素将出现在A(1:j-1)中; 若i>j，则A(1:n)中的第i小元素将出现在A(j+1:n)中顺序统计量:在一个由n个元素组成的集合中，第i个顺序统计 量(order statistic)是该集合中的第i小的元素。
中位数:对一个有n个元素的集合，将数据排序后，位置在最 中间的数称为该集合的中位数。
带权中位数:小于Xk的所有Xi的权重和小于0.5,大于Xk的所有Xi的权重和小于0.5* 最优化问题:这一类问题的可行解可能有很多个。每个解都有 一个评价优劣的值，我们希望寻找具有最优值的
解(最小值或最大值)。
* 最优子结构性:一个最优策略的子策略应是最优的.全局最优则局部最优
* 无后效性:如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。利用动态规划方法求解多阶段决策过程问题，过程的状态必须具备无后效性
* 剪切-粘贴”技术:本质上是反证法证明:假定原问题最优解中对应于某个子问题 的部分解不是该子问题的最优解，而存在“更优的子解”，那么我们 可以从原问题的解中“剪切”掉这一部分，而将“更优的子解”粘贴 进去，从而得到一个比最优解“更优”的解，这与最初的解是原问题 的最优解的前提假设相矛盾。因此，不可能存在“更优的子解”。
* 状态转移方程:阶段之间状态变量值的变化存在一定的关系。如果给定i阶段的状态变量x(i)的值后，第i+1阶段的状态 变量x(i+1)就可以完全确定，即x(i+1)的值随x(i)和第i阶段的 决策u(i)的值变化而变化，可以把这一关系看成(x(i)，u(i)) 与x(i+1)的函数关系，表示为:x(i+1)=Ti(x(i),u(i))这种从i阶段到i+1阶段的状态转移规律称为状态转移方程。15.1钢条切割(重点)
一.带备忘的自顶向下法
二.自底向上法(bottom-up method)
都具有相同的渐近运行时间: Θ(n2)。
15.2 矩阵链乘法(重点)
15.3 动态规划的一般方法(熟悉)
多阶段决策过程
要满足1.无后效性。2.最优化原理(最优子结构性):无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列.15.4 最长公共子序列(重点)
15.5 最优二叉搜索树(重点)
分步骤实施，它在每一步仅作出当时看起来最佳的选择，即局部最优的选择，并希望通过这样的 选择最终能找到全局最优解。
贪心选择:在贪心算法的每一步所做的当前最优选择就叫做贪心选择16.1活动选择问题(重点)
不失一般性，设活动已经按照结束时间单调递增排序.只需O(n)的时间即可选择出来n个活动的最大兼容活动集合.每次都选择结束时间最早的活动即可.
16.2贪心算法原理(重点)
通常采用自顶向下的设计.
贪心求解的一般步骤:
1)确定问题的最优子结构;
2)将最优化问题转化为这样的形式:每次对其作出选择后，只 剩下一个子问题需要求解;
3)证明作出贪心选择后，剩余的子问题满足:其最优子解与前 面的贪心选择组合即可得到原问题的最优解(具有最优子结构)。
贪心选择性质:可以通过做出局部最优选择(即贪心选择)来构造全局最优解的性质。
贪心算法更为直接地使用最优子结构:每次贪心选择后都得到一个子问题，而原问题的最优解就 是贪心选择和子问题的最优解的组合。能否成功，最优子结构 性质是根本保证。16.3 Huffman编码(熟悉)
动态算法和贪心算法的异同;
动态规划具有两个性质：1）重叠子问题2）最优子结构
贪心算法：1贪心选择性质2）最优子结构状态空间树:解空间的树结构称为状态空间树(state space tree)
◼ 问题状态:树中的每一个结点代表问题的一个状态，称为问题状态(problem state) 。
◼ 状态空间:由根结点到其他结点的所有路径确定了这个问题的状态空间(state space) 。
◼ 解状态:是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这个问题解空间中的一个元组.
◼ 答案状态:是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解.
◼ 周游:对每一个点进行检索22.1图的表示(熟悉)
有向图、无向图、邻接矩阵矩阵、邻接表
22.2 广度优先搜索(熟悉)
宽度优先检索
1 从结点v开始，首先访问结点v，并给v标上已访问标记。
2 访问邻接于v且目前尚未被访问的所有结点，此时结点v被检测，而v的这些邻接结点是新的未被检测的结点。将这 些结点依次放置到一个称为未检测结点表的队列中。
3 若未检测结点表为空，则算法终止;否则
4 取未检测结点表的表头结点作为下一个待检测结点，重复上述过程。直到Q为空，算法终止。
1.算法BFS可以访问由v可到达的所有结点
2.设t(n,e)和s(n,e)是算法BFS在任一具有n个结点和e条边的图G上所花的时间和附加空间。
● 若G由邻接表表示，则t(n,e)=Θ(n+e)和s(n,e)=Θ(n).● 若G由邻接矩阵表示，则t(n,e)=Θ(n2)和s(n,e)=Θ(n)
●t(n,e)=Θ(n+e) 使用邻接表表示 ●t(n,e)=Θ(n2) 使用邻接矩阵表示22.3 深度优先搜索(熟悉)
从结点v开始，首先访问v，并给v标上已访问标记;然后中止对v的检 测，并从邻接于v且尚未被访问的结点的中找出一个结点w开始新的检测。 在w被检测后，再恢复对v的检测。当所有可到达的结点全部被检测完毕后， 算法终止。
1 DFS可以访问由v可到达的所有结点
2 如果t(n,e)和s(n,e)表示DFS对一n结点e条边的图所花的 时间和附加空间，则
● s(n,e)=Θ(n)
● t(n,e)= Θ(n+e) G采用邻接表表示，或 ● t(n,e)= Θ(n2) G采用邻接矩阵表示!!!! 利用栈的宽度优先策略下的结点生成次序(D- Search)
回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标,就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
第一步:为问题定义一个状态空间，这个空间必须至少包含问题的一 个解
➢ 第二步:组织状态空间以便它能被容易地搜索。 典型的组织方法是图或树。
➢ 第三步:按深度优先的方法从开始结点进行搜索
➢ 开始结点是第一个活结点(也是E-结点:expansionnode)
➢ 如果能从当前的E-结点移动到一个新结点，那么这个新结点将变成一个活结点和新的E-结点，旧的E-结点仍是一个活结点。
➢ 如果不能移到一个新结点，当前的E-结点就“死”了.不再是一个活结点.那么便只能返回到最近被考察的活结点.四皇后 —— (回溯求解) 限界函数 开始状态 结点的生成
子集和数问题:已知n个正数的集合W={w1, w2, ..., wn}(按照非降次序排列)和正数M。要求找出W中的和数等于M的所有子集。
k-元组(用元素下标表示):(1，2，4)和(3，4)/n-元组(用n元向量表示):(1，1，0，1)和(0，0，1，1)
是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含 答案结点子树的状态空间的检索方法。
(回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T)
限界函数:在结点生成的过程中，定义一个限界函数，用 来杀死还没有全部生成儿子结点的一些活结点
* LC-检索:选择 cˆ(•)值最小的活结点作为下一个E-结点的状态空间树检索方法。
* LC分支-限界检索:伴之有限界函数的LC-检索
成本越小越优先。
对任一结点X，可以用两种标准来衡量结点的代价:1)在生成一个答案结点之前，子树X需要生成的结点数。 2)在子树X中离X最近的那个答案结点到X的路径长度。
◼ 结点成本函数:C(·) 有答案结点,则该子树成本都为答案结点,如果没有答案结点,则C(x)=∞
◼ gˆ(X):是由X到达一个答案结点所需成本的估计函数
◼ h(X):根结点到结点X的成本——已发生成本。引进h(X)改进成本估计函数。
◼ cˆ(X)= f(h(X))+gˆ(X)(避免单纯考虑 gˆ(X)造成的纵深检查)(改进的结点成本估计函数;)
对具有 cˆ( X ) U 的所有活结点可以被杀死，从而可以进一步使算法加速，减少求解的盲目性
◼ 定义U为最小成本解的成本上界，则:对具有 cˆ( X ) U 的所有活结点可以被杀死，从而可以进一步使算法加速，减少求解的盲目性。◼概念:具有最小权重的生成树称为最小成本生成树，简称最小生成树。它并不一定唯一
处理策略:每一步我们选择一条边不违反循环不变式的边(u,v)加入集合A，即A∪{(u,v)}仍是某棵最小生成树的子集。
◼安全边:这样的边称为“安全边”，因为在集合A中加入它不会破坏A的循环不变式。
◼切割:无向图G=(V,E)的一个切割(S,V-S)是结点集V的一个划分。
◼横跨切割:如果一条边(u,v)∈E的一个端点在集合S中，另一个端点在集合V-S中，则称该条边横跨切割(S,V-S)。
◼轻量级边:在横跨一个切割的所有边中，权重最小的边称为轻量级边。◼Kruskal算法:集合A是一个森林，其结点就是给定图的结点， 每次加入到集合A中的安全边是连接两个不同分量
的权重最小的边。(典型贪心算法)
Kruskal算法的运行时间依赖于不相交集合数据结构的具体 实现。◼ Kruskal算法的时间为:O(ElgE )。
◼Prim算法:集合A是一棵树，每次加入到A中的安全边是连接A和 A之外某个结点的边中权Prim算法的时间为:O(VlgV +ElgV)=O(ElgV)。重最小的边。(典型贪心算法)
◼Prim算法的时间为:O(VlgV+ElgV)=O(ElgV)。24.1 Bellman-Ford算法(重点)
松弛操作:首先测试一下是否可以对从s到v的最短路径进行改善(即有没有更短的路径)。如果可以改善，则v.d更新
为新的最短路径估计值,v的前驱v.π更新为新的前驱结点。
Bellman-ford算法可以求解一般情况下的单源最短路径问题 — 可以有负权重的边，但不能有负权重的环。
24.3 Dijkstra算法(重点)
Dijkstra算法是一个贪心算法:每次总是选择V-S集合中 最短路径估计值最小的结点加入S中。24.4 差分约束和最短路径(重点)
◼线性规划:给定一个m*n的矩阵A、一个m维的向量b和一个n维 的向量c。试找一n维向量x，使得在Ax≤b的约束下， 目标函数最大。24.5 最短路径性质的证明(熟悉)
最短路径的最优子结构性:两个结点之间的最短路径的任何子路径都是最短的。
◼2.上界性质: v.d是s到v的最短路径权重δ(s,v)的上界
引理24.11 设G=(V,E)为一个带权重的有向图，其权重函数为w:E→R，设源结点为s，该图由算法 INITIALIZE-SINGLE-SOURCE(G,s) 执行初始化。那么对于所有的结点v∈V，v.d≥δ(s,v)。并且该不变 式在对图G的边进行任何次序的松弛过程中都保持成立，而一旦 v.d取得其下界δ(s,v)后，将不再发生变化。
用数学归纳法证明:对于所有的结点v∈V，v.d≥δ(s,v)。 ➢ 注:归纳的主体是松弛步骤的数量。
基础步:INITIALIZE-SINGLE-SOURCE(G,s)中进行初始化时，对于所有的结点v∈V-{s}，置 v.d=∞,而s.d=0 ，显然s.d≥δ(s,s)，而其它的结点 v.d≥δ(s,v)，结论成立。
归纳步:考虑对边(u,v)的松弛操作。 假设在对边(u,v)进行松弛之前，对所有的结点x∈V，都有
x.d≥δ(s,x)。◼3.非路径性质
给定一个带权重的有向图G=(V,E)，其权重函数 为ω:E→R。假定从源结点s到给定点v之间不存在路径，则该图 在由算法 INITIALIZE-SINGLE-SOURCE(G,s) 进行初始化后，有
v.d≥δ(s,v)=∞， 并且该等式作为不变式一直维持到图G的所有松弛操作结束。
证明: 因为从源点s到给定点v之间不存在路径，所以δ(s,v)=∞。
而根据上界性质，总有v.d≥δ(s,v)，所以，v.d≥δ(s,v)=∞。 得证。◼4.收敛性质
G=(V,E)为一个带权重的有向图，其权重函 数为ω:E→R。设s∈V为某个源结点,s~-> u -> v为图G中从s到v的一条最短路径(u,v∈V)。
证明:根据上界性质，如果在对边(u,v)进行松弛前的某个时刻有u.d = δ(s,u),而根据上界性质，有v.d≥δ(s,v)。所以有v.d=δ(s,v)，并且 该等式在此之后一直保持成立。◼5.路径松弛性质
设G=(V,E)为一个带权重的有向图，其权重函 为ω:E→R。设s∈V为某个源结点，考虑从源结点s到结点vk
的任意一条最短路径p=<v0,v1,...,vk>，v0=s。
归纳法证明:在最短路径p的第i条边被松弛之后，有vi.d=δ(s,vi)
基础步:在对路径p的任何一条边进行松弛操作之前，从初始化算法可以得出:v0.d=s.d=δ(s,s)。结论成立， 且s.d的取值在此之后不再发生变化。
归纳步:假定依次经过(v0,v1)、 (v1,v2)、...、(vi-2,vi-1) 松弛操作之后，vi-1.d=δ(s,vi-1)。
则在对边(vi-1,vi)进行松弛操时，根据收敛性质,必有在对该边进行松弛后vi.d=δ(s,vi)，并且该等式 在此之后一直保持成立。◼6.前驱子图
一个源点s所诱导的前驱子图定义为Gπ=(Vπ，Eπ)，其中，
➢ 结点集合Vπ={v∈V:v.π≠NIL}∪{s}
➢ 即Vπ是源点s和图G中的前驱结点不为NIL的所有结点的集合。
➢ 边集合Eπ={(v.π,v)∈E:v ∈Vπ-{s}}
➢ 即Eπ是由Vπ中的结点v的π值所“诱导”(induced)的边的集合。
则，算法终止时，Gπ是一棵最短路径树。25.2 Floyd-Warshall(重点)(复杂度Θ(V^3))
25.3 用于稀疏图的Johnson算法(重点)
◼稀疏图，Johnson算法优于Floyd-Warshall算法，时间复杂度可达O(V^2*lgV+VE)。
使用Bellman-Ford算法和Dijkstra算法作为子程序 来计算所有结点之间的最短路径。
有一个源结点和一个汇点，从源结点向汇点“运输”货物。在不违反任何路径容量限制的条件下，从源结点到汇点运送 货物的最大速率是多少——这一问题的抽象称为最大流问题。
26.1 流网络(重点)
-
标准流网络:无反向边、只有单一的源结点和汇点
-
容量限制、流量守恒
26.2 Ford-Fulkerson方法(重点)
◼通过不断增加可行流值的方式找到最大流: (1)从流值为0的初始流开始;(2)通过某种方法对流值进行增加; (3)当确认无法再增加流值时，就得到最大流;
* 每次循环做三个主要操作，计算残存网络、寻找增广路径和更新每条边的流值。
-
残存网络:
-
增广路径:给定流网络G=(V,E)和流f ，增广路径p(Augmenting Path)是其残存网络Gf中一条从源结点s到汇点t的简单路径。
最大流最小切割定理:设f为流网络G=(V,E)中的一个流，该流网络的源结点为s，汇点为t，则下面的条件是等价的: (1)f是G的一个最大流 (2)残存网络Gf 不包括任何增广路径 (3)|f|=c(S,T)，其中(S,T)是流网络G的某个切割
◼Edmonds-Karp算法:使用广度优先搜索寻找源结点到汇点的最短路径作为增广路径。
引理4:如果Edmonds-Karp算法运行的流网络 G = (V , E ) 上，该网络的源结点是s汇点为t，则对于所有结点 v属于V −{s,t} ，残存网络 Gf中的最短路径距离f(s,v) 随着每次流量的递增而单调递增
- 证明:假设对于某个结点 v属于V −{s,t}，存在一个流量递增操作，导 致从源结点s到v的路径距离减小。
设f 是第一个导致某条最短路径距离减少的流量递增操 作之前的流量，f' 是递增操作之后的流量。
设v是在流递增操作中最短路径被减小的结点中δf'(s, v) 最小的结点，根据假设，应有δf'(s,v)<δf(s,v)。 下面证明这个不等式不成立。