final exam review

Backtracking

思想

决策过程的形式化：构建决策树，进行剪枝

例子

八皇后问题

$8\times 8$格子上放8皇后，每行/列/斜线上仅有一个皇后。先在第一列放，然后考虑第二列可行放法，再考虑第三列，依次向后面的列放置，如果有哪步不行则回退到上一列考虑其他放法。

收费公路问题(turnpike reconstruction)——NP-complete

问题描述：给定一个点集中点的两两之间距离，要求重构出点集中各点位置。我们只需要知道点的分布即可。首先确定距离最远的两个点，然后确定距离次远的两个点（次远距离肯定是中间某个点与端点的距离，因为如果是中间两个点距离次远，那么可以连接这两个点然后任意向一端延伸到端点，得到更远的距离，与次远距离矛盾）。我们根据距离从远到近依次确定各点的位置，当加入一个与端点距离为$d_i$的点后，这个点都会和已存在的所有$k$个点产生$k$个距离，我们要将这$k$个距离从给出距离集合中去掉，如果有某个距离再距离集合中不存在，说明这个点放错了，它应该放在放在与另一个端点距离为$d_i$的地方，如果还不行则回溯到上一个点，改变上一个点的放置。

最大最小搜索

Divide and conquer

主定理

主定理：$T(n)=aT(\frac{n}{b})+f(n)$ n是问题规模大小； a是原问题的子问题个数； $n/b$是每个子问题的大小，这里假设每个子问题有相同的规模大小； $f(n)$是将原问题分解成子问题和将子问题的解合并成原问题的解的时间。

主定理

若$n^{log_ba}>f(n)$，则$T(n)=\Theta(n^{log_ba})$
若$f(n)$更大，且满足规范化条件$af(n/b)\leq cf(n)$，则$T(n)=\Theta(f(n))$
若两函数相等，则$T(n)+\Theta(n^{log_ba}log^{k+1}n)$

方程 $ af\left(\frac{N}{b}\right) = f(N) $，即表示 子问题的工作量的总和 $a \cdot f\left(\frac{N}{b}\right)$ 恰好等于 当前问题的工作量 $f(N)$ 这意味着，递归树的每一层的总工作量相等。在这种情况下，$ f(N) $ 的增长速度与递归树的深度是平衡的，因此，递归深度与每一层的工作量相乘，整体的复杂度将是 $ \Theta(N^{\log_b a} \log N) $，对应于主定理的2

更强的形式

alt text

与之前的主定理不同在于第二种情况。

还可以加强：

alt text

递归树

alt text

总时间等于各层合并时间加上叶节点处理时间

应用： alt text

例子

最大子序列和

寻找一个数组中和最大一个子序列：分为两部分A,B，将A,B各自的最大子序列和跨A,B两个部分的最大子序列和大小比较，跨A,B两个部分的最大子序列和求解是线性时间，因为从原数组的中间向左右两边遍历寻找即可。

$T(n) = 2T(n/2) + O(n)$ 时间复杂度：$O(nlogn)$

逆序对计数

一个数组的逆序对是指，对于数组中的两个元素 $A[i]$ 和 $A[j]$，如果 $i < j$ 且 $A[i] > A[j]$，则称 $A[i]$ 和 $A[j]$ 构成一个逆序对。

算法：在归并排序的合并过程中可以计数逆序对。若已将数组划分为两部分A,B且分别排好序，则逆序对等于A,B各自逆序对个数加上跨A,B的逆序对个数，这个跨A,B的逆序对个数可以在合并过程中计数：

while(i<n&&j<n){
    if(i<n&&j<n&&A[i]<=B[j]){
        C[k++]=A[i++];
    }else if(i<n&&j<n&&A[i]>B[j]){
        inv_cnt+=n-i;
        C[k++]=B[j++]
    }
}
...//复制A或B中没完成的部分

乘法和矩阵乘法

一般的竖式乘法时间复杂度为O(n^2)，我们可以把两个n位乘数$a,b$ 写为 $a=10^{n/2}a_1+b_1,b=10^{n/2}a_2+b_2$，这样$a_i,b_i$为n/2位乘法，实现了分治，而 [ab=10^na_1a_2+10^{n/2}(a_1b_2+a_2b_1)+b_1b_2]

\[a_1b_2+a_2b_1=(a_1+a_2)(b_1+b_2)-a_1a_2-b_1b_2\]

分治后总需算3次乘法。所以：$T(n)=3T(n/2)+O(n)$,时间复杂度为$O(n^{log_23})$

Dynamic programming-动态规划

基本概念

是一种求解复杂问题的算法设计方法，特别适用于那些可以分解为子问题的优化问题。动态规划算法通过将原问题分解为更小的子问题来解决，并将每个子问题的解存储起来，避免重复计算，从而提高效率。

最优子结构：问题的最优解可以通过子问题的最优解来构造。也就是说，原问题的解是其子问题解的某种组合。
重叠子问题：不同的子问题会重复计算相同的子问题。动态规划通过缓存已经计算过的子问题的结果来避免重复计算，从而提高效率。

问题

Fibonacci数计算

基本问题：求Fibonacci数$F(n)=F(n-1)+F(n-2)$:递归求解时，由决策树可知，F(n-1)和F(n-2)均计算了$F(n-3),F(i),i<n-3$ 等，存在大量重复计算，所以可以用一张表将已经计算的结果保存下来，可以保存1~n的所有Fibonacci数，也可以只保存最后计算的那两个。

f0=1
f1=1
for i in range(n-1):
    f=f0+f1
    f0=f1
    f1=f
#保存所有数
f=[0 for _ in range(n+1)]
f[0]=f[1]=1
for i in range(2,n+1):
    f[i]=f[i-1]+f[i-2]

最长公共子序列

给定两个字符串，要求找出它们的最长公共子序列（LCS），即两个字符串中都有的字符，且这些字符在两个字符串中出现的顺序一致。

加权独立集合问题

考虑一维情况：给定一个图$G=(V,E)$，和每个节点的权重$w(v_i)$，要求找到一个独立集合$I\subset V$，使得I中节点间无任何边相连且权重和最大。动态规划方程：仅无负权重情况。 $W_n=max\{W_{n-1},W_{n-2}+wn\}$

alt text

从伪代码来看，如果有负权重，比如$w_1=-3,w_2=-1$，那么第一次循环会得到$A[2]=-1$，这是错的，因为它最大可以是0，即什么也不选。

最大子序列和问题2

定义$dp[i]$为以第i个元素为结尾的最大子序列和 [dp[i]=max{dp[i-1]+w_i,w_i}] O(n)时间求出dp[i],i=0,..n，然后遍历dp[i]找出最大的那个，比如为dp[k]。找出这个和最大的子序列：从dp[k]向前遍历，判断$dp[t]=dp[t-1]+w_t,t=k,...0$是否成立，如果成立，说明子序列可以继续向前扩充，如果不成立说明最大和子序列中止于$t$

O(n)

零钱兑换问题

alt text

定义$dp[i]$为i元钱所需的最少硬币，则动态规划方程为$dp[i]=min\{dp[i],dp[i-coin]+1\} for coin in coins$，即将当前问题转化到总钱数为$i-coin$的已解决问题上，不断遍历$coin$。

alt text

O(n) 如何构造出兑换方式：我们需要追踪dp[amount]是如何被取到的，它是由min{dp[amount-coin]+1}, for coin in coins,决定的，我们需要找到它转化时对应的coin，然后再考虑dp[amount-coin]转化到更少钱数时对应的coin，所以可以在更新每个dp[i]时记录它们最后一次转化（也就是用硬币最少的情况）时的coin。

背包问题

0-1背包问题：我们有 n 个物品，每个物品的重量为 si，价值为 vi，我们有一个容量为 C 的背包，我们希望找到一个最优的装载方案，使得背包中的物品总价值最大。定义$dp[i][j]$为容量为i的背包在考虑前j个物品时可装的最大价值， $i>s_j$:

\[dp[i] [j]=max\{dp [i-s_j] [j-1] + v_j,dp [i] [j-1]\}\]

$i<s_j$:即背包放不下第j个物品

\[dp[i] [j]=dp[i] [j-1]\]

矩阵连乘问题

我们考虑矩阵链相乘 M1M2 · · · Mn，每个矩阵的大小为 $r_i−1 × r_i$。对于n个矩阵整体而言，它最终还是要化为两个矩阵乘法:$M_{1,i}*M_{i+1,n}$，用$m_{1n}$表示从M1乘到Mn所用的最少乘法次数，则 [m_{1n}=\min\limits_{1\leq k\lt n}{m_{1,k}+m_{k+1,n}+r_0r_kr_n}]

进一步推广可得： [ m_{ij}= \begin{cases} m_{ij}=\min\limits_{i\leq k\lt j}{m_{i,k}+m_{k+1,j}+r_{i-1}r_kr_j} & i<j\ 0 & i=j \end{cases} ]

时间复杂度为$O(n^3)$

最优二叉搜索树

alt text

\[c_{ij} = \sum\limits_{k=i}^{j} + \min\limits_{i⩽k⩽j}\{c_{i,k−1} + c_{k+1,j}\}, i ⩽ j.\]

第一项的意义在于，因为根结点的存在，导致所有 i 到 j 的单词都加深一层，是两个子问题结合起来增加的代价。第二项则是左右子树子问题的情况。

伪代码如下：

alt text

$O(n^3)$

最短路径问题

Greedy

活动选择问题

alt text

贪心策略：将活动按结束时间从早到晚排序，依次选择活动，如果当前活动不与之前活动冲突，则选择它。等价策略：从后往前依次选择不冲突的最晚开始的活动。

调度问题

假设我们现在有 n 个任务，每个任务 i 都有一个正的完成需要的时间 li 和一个权重 wi。假定我们只能按一定顺序依次执行这些任务，不能并行。记任务i完成时间为$C_i(\sigma)$,它等于调度开始到它被完成的时间。目标为最小化所有任务的加权完成时间之和： [T=\min\limits_{\sigma}\sum\limits_{i=1}^{n}w_iC_i(\sigma)] 贪心方式：尽可能先放权重大的时间短的，计算每个任务的$w_i/l_i$按从大到小调度。

Optimal prefix code(最优前缀编码)

编码树

满二叉树：所有节点要么是叶子要么有两个儿子
最优前缀码的编码树一定是一棵满二叉树：最优前缀码（如霍夫曼编码）要求每个叶子节点都处于树的最底层或接近最底层。如果二叉树是非满的，某些叶子节点可能会出现在较高的层级，这就违反了最优前缀码的构造要求：频率较高的符号应该被分配较短的编码，意味着它们应该位于较低的层级。

Huffman编码

寻找出现频率最低的两个节点，用一个空节点将它们连接，频率小的放左边，大的放右边，空节点频率为被连接的两个节点的频率和。这样，所有字符最终连接到一棵二叉树上，且字符为叶节点。

哈夫曼树编码k个字符，树的节点个数为：叶节点+非叶节点=k+k-1=2k-1。

非叶子节点由合并而来，k个节点最终合并为1棵树需要合并k-1次。

K-聚类问题

一种无监督机器学习问题目标：最大化类间间距（定义为两类中距离最近点对的距离）（实际上等价于最小化类内（到中心）距离）。贪婪算法：计算任意两点间距离，排序，依次将最小边连上，直到剩下K个联通分量（与Kruskra算法生成最小生成树相同）。

NP

alt text

概念

NP NP类问题是指那些可以在非确定性图灵机上在多项式时间内解决的问题，等价于：只要求能在多项式时间内验证解，
NP-complete 是 NP 问题中最难的一类，意味着如果我们能解决一个 NP-complete 问题，那么所有 NP 问题都能被解决，即所有NP问题可以归约到NPC问题。
NP-hard 是所有最难问题的集合，这些问题可能并不属于 NP 类，也就是它们的解有可能不能在多项式时间内验证，或者根本就没有多项式时间的验证过程。
co-NP:NP问题的对偶，给定一个反例（即问题的负面解），我们可以在多项式时间内验证这个反例的有效性。例子：3-SAT的对偶问题：给定一个布尔公式，判断是否不存在任何一个变量赋值使得该公式为真。

归约（reduction）

A language L1 is polynomial-time reducible to a language $L2 ( L1 \leq_p L2 )$ if there exists a polynomial-time computable function $f : \{0, 1\}* → \{0,1\}*$ such that for all $x \in{0, 1}*, x\in L1 $ iff $ f(x) \in L2$. $A \leq_P B$表示A可多项式时间归约到B，意味着A不比B难，或者B至少和A一样难

基本思想

归约的核心思想是：如果我们能够将一个已知难度的 问题 A 转化为另一个问题 B，并且能有效地求解问题 B，那么问题 A 也就变得可解了。通过归约，我们可以利用已经解决的更简单或已知更难的问题来解决更复杂的问题。

归约通常有两种形式：

多项式时间归约：指将一个问题转化为另一个问题的过程所需的时间是多项式级别的，即对于输入的大小 $n$，转换的时间复杂度是 $O(n^k)$，其中 $k$ 是常数。
可判定归约：指通过归约，问题可以在多项式时间内得到解决。

归约的具体过程

输入转换：将问题 $A$ 的输入转换成问题 $B$ 的输入。转换必须在多项式时间内完成。
求解问题 $B$：用已知的算法求解问题 $B$。
输出转换：将问题 $B$ 的解转换回问题 $A$ 的解。这个过程也必须在多项式时间内完成。

归约的应用

证明问题的 NP-hard 性：为了证明一个问题是 NP-hard，通常的做法是将已知的 NP-hard 问题归约到该问题。如果一个已知的 NP-hard 问题能在多项式时间内归约到某个问题 $A$，那么问题 $A$ 就是 NP-hard 的。
例如，我们可以通过将 旅行商问题（TSP） 或 背包问题（Knapsack Problem） 等已知的 NP-hard 问题归约到某个新问题，来证明新问题是 NP-hard 的。
设计优化算法：有时归约可以帮助我们设计优化问题的近似算法，特别是在解答复杂问题时，归约帮助我们通过利用已有的解法来减少求解复杂度。

归约的例子

1. TSP（旅行商问题）归约到哈密尔顿回路问题

假设你知道旅行商问题是 NP-complete 的。我们可以通过 多项式时间归约 将 旅行商问题（TSP） 归约到哈密尔顿回路问题，来证明Hamiltonian问题也是 NP-complete 的。

具体来说，如果我们有一个带权图，并且要求找到一条路径使得总权重最小且访问每个节点恰好一次，回到起点，那么我们可以将其转化为哈密尔顿回路问题。在哈密尔顿回路问题中，我们仅关心是否存在一条不重复经过每个节点的回路，不考虑边的权重。通过适当的转换，我们就能把旅行商问题转化为哈密尔顿回路问题，并证明它的难度。

2. 3SAT 归约到独立集问题

假设你想证明 独立集问题（Independent Set Problem） 是 NP-complete 的。你可以通过将已知的 NP-complete 问题 3SAT（3-可满足性问题） 归约到独立集问题来证明。3SAT 问题是给定一个布尔公式，判断是否存在一种变量的赋值使得公式为真。通过合理的多项式时间转换，将 3SAT 问题转化为一个独立集问题，证明独立集问题是 NP-complete 的。

归约的分类

多项式时间归约（Polynomial-time Reduction）：这是最常见的归约类型。如果问题 $A$ 可以在多项式时间内归约到问题 $B$，并且我们知道 $B$ 是 NP-hard 的，那么我们可以推断 $A$ 至少是 NP-hard 的。
多项式时间可归约（Polynomial-time Reducible）：如果问题 $A$ 可以在多项式时间内归约为问题 $B$，我们说 $A$ 是可归约的。这样的归约帮助我们证明一个问题的难度。
归约到优化问题（Reduction to Optimization Problems）：在优化问题中，常常将一个问题归约为其对应的决策问题，然后通过求解决策问题来优化解。

问题

SAT(可满足性问题)——NPC

给定一个布尔公式（通常是合取范式），可满足性问题求判断是否存在一个变量的赋值，使得整个公式的值为真。

特例：3SAT问题NPC：合取范式的每个子句中最多有三个变量。

Vertex cover(顶点覆盖)——NPC

顶点覆盖问题：给定图 $ G = (V, E) $，寻找一个最小的顶点集合 $ C \subseteq V $，使得对于每条边 $ (u, v) \in E $，要么 $ u \in C $，要么 $ v \in C $。

Donimatiing set(支配集)——NPC

支配集问题：给定图 $ G = (V, E) $，寻找一个最小的顶点集合 $ D \subseteq V $，使得对于每个 $ v \in V $，如果 $ v \notin D $，则存在一个顶点 $ u \in D $，使得 $ (u, v) \in E $，即 $ u $ 和 $ v $ 是邻居。

注意与顶点覆盖问题的不同，这里注重的是顶点的支配关系，而顶点覆盖注重的是边的覆盖。比如一个三角形环，顶点覆盖问题需选两个顶点而支配集问题只需选一个顶点。

Hamiltonian curcuit——NPC

哈密顿回路的定义：图中存在一个回路（闭合路径），它包含图中的每个顶点且每个顶点恰好出现一次。

TSP(旅行商问题)

优化版本（NP-hard）：给定一个完全图 G = (V, E)，每条边 e ∈ E 有一个权重 w(e)，求一条经过所有点的最短路径，即一条权重之和最小的哈密顿回路。
不可近似性：除非P=NP，否则对于任意$k\geq 1$，TSP不存在k-近似算法，但是添加了度量空间的条件后有如下结论：
判定版本（NPC）：要求判断是否存在一个哈密顿回路，其总权重不超过一个给定的阈值C。

Approximation-近似算法

对于不能同时满足下面三个特性的NP问题来说，如果满足了23但不满足1，那么就是近似算法。

1.optimality(找到最优解)
2.efficiency(多项式时间完成)
3.all instances(通用)

概念

近似比

近似比：

alt text

PTAS

PTAS（Polynomial Time Approximation Scheme）是一种用于求解优化问题的算法框架，它在多项式时间内提供接近最优解的近似解。具体来说，PTAS 是一种算法，它能够在多项式时间内对于任何给定的误差参数$\epsilon$提供一个问题的近似解，且这个解的质量与最优解的误差比例小于$1+\epsilon$，即相对于最优解的误差率为

时间复杂度：算法的时间复杂度是多项式级别的，但随着 $ \epsilon $ 的减小，时间复杂度可能会依赖于 $ \frac{1}{\epsilon} $。因此，对于小的 $ \epsilon $，PTAS 可能需要较长的运行时间，但仍然是多项式时间内的可接受解。
近似性：对于任何给定的 $ \epsilon > 0 $，算法输出的解的质量在最优解 $ OPT $ 的 $ (1 + \epsilon) $ 倍之内。换句话说，算法输出的解 $ A $ 满足： [ (1 - \epsilon) \cdot OPT \leq A \leq (1 + \epsilon) \cdot OPT ]
适用范围：PTAS 通常适用于 NP-hard 问题的近似求解。
FPTAS（Fully Polynomial-Time Approximation Scheme）：
FPTAS 是一种特殊类型的 PTAS，它不仅可以近似优化问题，而且其时间复杂度与 $ 1/\epsilon $ 相关，但仍然是多项式的，即时间复杂度是多项式函数，既与输入大小有关，也与 $ 1/\epsilon $ 有关。
FPTAS 适用于一些具有特殊结构的优化问题（如线性规划问题）。

最小化工时调度问题

一维装箱问题

NF,FF,BF

0-1背包

K聚类问题2

问题描述：最小化类内间距（之前是最大化类间间距）：输入 n 个点的位置 s1, · · · , sn，以及一个整数 k，要求选择 K 个中心，使得每个点到最近的中心的距离最大值 r(C) 最小化。

Greedy-2r算法

假设我们知道了r(C)的最小值为r，那么我们可以每次从点集中选取一个点作为中心，把它加入中心点集，然后删除以这个点为中心半径为2r的圆内的所有点，算法必在k步内中止。为什么k步内中止：由假设知当r(C)为r时我们可以选出k个中心进行聚类，每个类半径为r，那么任意一个点s必然在以某个点$C*$为圆心半径为r的圆内，当以点s为圆心半径为2r作圆时，这个圆会包含圆$C*$中的所有点，所以将2r圆范围内点删去至少会减少一个类，所以K步之内必然中止。
Greedy-2r算法在给定最优解r(C)的情况下为2-近似算法。但是最优解r(C)未必给定，所以我们需要不断尝试使用二分查找选择r(C)，如果选的r(C)不能使算法在K步内中止，那么说明r(C*)选小了。

Greedy-Kcenter算法

我们首先从输入点集中随机选取一个点作为第一个中心，加入中心点集 C。然后每轮循环在剩余的点中找到一个点 s 的 dist(s, C) 最大，即 s 是到现有中心最短距离最大的点，将其加入中点集C，直到 C 中有 K 个点。这一算法的近似比是 2。

聚类问题最优近似比

定理：除非 P = NP，否则 K-center 问题不存在 ρ-近似算法（ρ < 2）。证明是将NPC问题dominating set归约到k-center问题。 dominating set 问题：给定一个图 G = (V, E)和一个整数 k，我们需要判断是否存在一个大小为 k的集合 S ⊂ V ，使得每个点要么在 S 中，要么与S 中的某个点相邻。

Local search-局部搜索

问题

顶点覆盖问题

贪心算法：选取任意一条边 (u, v)，将 u 和 v 同时加入到 C 中，然后把 u 和 v 所在的所有边全部移除，下一轮继续在剩下的边中随机选择一条重复上述操作，直到所有的边都被删除为止。这个算法的近似比为2。
梯度下降：首先定义解的“邻居”：比当前解少一个顶点的解。所以算法流程可以是：设解的顶点集为S，从所有顶点出发，令S=V，逐步从S中减去一个顶点v，然后检查S-{v}是否仍未一个覆盖。
模拟退火：

alt text 这个过程中T逐步减少即为模拟退火。

Hopfield神经网络的稳定构型

首先给出一些定义：

alt text

我们称一个构型是稳定的，当且仅当所有点都是满意的。问题：给定一个 Hopfield 神经网络，是否存在一个稳定构型？如果存在，如何找到这个稳定构型？算法：

alt text

可以证明这个算法有限步会中止，最多翻转$\sum\limits_{e\in E}|w_e|$

最大割问题

割边权重和最大：

alt text

算法（转化为Hopfield神经网络稳定构型问题）：

alt text

random algorithm

parallel algorithm-并行算法

PRAM（parallel random access machine）模型

多个处理器共享一个公共内存，并且每个处理器都可以访问这个共享内存

共享内存：所有的处理器可以访问共享内存，没有明确的分布式内存系统的概念。 无限并行处理器：PRAM 假设有无限数量的处理器，因此可以在理论上同时进行大量的计算。实际情况中，处理器数量是有限的，但PRAM模型通常用来分析并行算法的理想性能。同步：所有的处理器在同一时刻执行指令，但内存访问有不同的访问规则。

根据内存访问类型分类

EREW (Exclusive Read Exclusive Write)：每个处理器在某一时刻只能读写内存中的不同位置，不能同时读取或写入同一个位置。 CREW (Concurrent Read Exclusive Write)：允许多个处理器同时读取同一内存位置，但写操作仍然是排他的。 CRCW (Concurrent Read Concurrent Write)：允许多个处理器同时读取和写入同一内存位置，通常需要额外的同步机制来避免冲突。

WD（work depth）

work:衡量计算总量
depth:衡量最长依赖路径，决定了并行计算的上界 $T_{para}=\frac{W(n)}{P(n)}+T(n)$ n可以表示问题规模，W(n)为工作总量，P(n)为处理器数量， T(n)为Depth，并行化上界。当P(n)较小时，时间由前一项决定，问题较大时并行时间由后一项决定。

求和问题

alt text

求和问题的Work-Depth presentation:

Work-Depth

$T(n)=logn+2， W(n)=n+n/2+n/2^2+\cdots n/2^k+1=2n, 2^k=n$ W(n)相当于计算树的节点个数

前缀和问题

在基本的求和树上新定义$C(h,i)=\sum\limits_{k=1}^{\alpha}A(k)，A(k)即输入的所有数，(0,\alpha)$ 为当前节点$(h,i)$的子树中的最右下的节点。

思路：在已经构造出的求和树中，从根节点向下计算，每层并行计算。根节点C值（前缀和）等于B值（求和问题中的和），之后的每一层（除最底层）：
第一个节点$(h,1)$的C值等于B值
偶数节点（右儿子）的前缀和等于父节点的前缀和。
奇数节点（左儿子，除第一个节点）$C(h,i)=C(h,i+1)-B(h,i+1)$，但是$C(h,i)$和$C(h,i+1)$为同时计算，这样会出错，重新考虑:$C(h,i)=C(h+1,(i-1)/2)+B(h,i)$ 代码如下：

$T(n)=O(logn),W(n)=O(n)$

合并非递减数组问题

即合并大小为n的A，B为C，保持非减.

解法

定义$Rank()$，将排序问题转化一下:

可见上面 RANK(j,A) 的值表示$B[j]$在A数组中的大小排名，也说明了A中有多少个比B[j]小的元素。同理 RANK(j,B) 的值表示$A[j]$在B数组中的大小排名。如果有了RANK，就知道了A,B中元素在合并后数组中的位置，那么就可以用$O(1)$的时间和$O(n+m)$的工作量完成合并：

那么现在的问题是如何求RANK，下面给出并行和串行算法：

下面基于Serial ranking来优化出更高效的算法：

先分割且计算选中元素的RANK（可以并行用二分搜索），然后对分割后形成的最多2p个区域（两条相邻连线中间的区域）进行并行计算RANK，每个都用Serial ranking

寻找数组中最大值问题

法1：并行比较所有$n^2$对数，大的赋值为0，小的赋为1，然后并行查看n个数0，1情况，是0的就是最大数（比较并赋值过程可能有访问冲突）

法2：$\sqrt n$分割

法3：$loglogn$分割

法4：规模$n^{7/8}$随机采样，然后先按$n^{1/8}$大小分割为$n^{3/4}$块，每块通过法1并行得到最大值，就有了$n^{3/4}$个值重新比较大小，再将它按$n^{1/4}$大小分为$n^{1/2}$块，最后这$n^{1/2}$块通过法1比较大小，$T(n)=O(1),W(n)=O([n^{1/2}]^2)=O(n)$

但是随机的$n^{7/8}$规模数据中可能不包括最大值，所以要将得到的最大值与剩下所有的$n^{1/8}$个数据按$O(1)$时间比较大小，如果有比它大的则将$n^{1/8}$个数加入重新随机。

External sorting

多路合并

减少了合并的次数，但是所需磁带增加，k-way:2k个磁带工作（与磁带交互）趟数：$1+\lceil \log_k{(N/M)}\rceil$

缓存并行处理

k路合并时，需要2k个磁带，也需要2k个输入缓存区和2个输出缓存区。

多路合并并不是磁带越多越好，k路合并时应当将整个内存区域划分成 2k 个输入缓存区合 2 个输出缓存区，这样当 k 很大的时候，我们的输入缓存就会被划分得很细，一次能读入输入缓存的数据量就会减小（也就是 block 大小降低），那么我们的 I/O 操作就会变多。

多相合并（Polyphase）

使每个磁带上顺串个数为相邻的Fibonacci数，比如读入34个顺串可以将其中13个读入另一个磁带进行合并。

Replacement Selection-替换选择

优化顺串（每组排序好的记录）的构造，以往顺串：根据内存大小来定，固定数目地取。现在：内存中维护一个优先队列，每次从队列中取出第一个比当前顺串中最后一个元素更大的元素，写入磁盘，然后再从磁盘中读入一个元素放入队列中，直到队列中的元素都比顺串的最后一个要小，就开启一个新的顺串。所以顺串的长度不定，但是不影响合并。

优化顺串合并：Huffman树，每次合并最短的两个顺串。

final exam review

Backtracking

思想

例子

八皇后问题

收费公路问题(turnpike reconstruction)——NP-complete

最大最小搜索

Divide and conquer

主定理

更强的形式

递归树

例子

最大子序列和

逆序对计数

最近点对问题

乘法和矩阵乘法

Dynamic programming-动态规划

基本概念

问题

Fibonacci数计算

最长公共子序列

加权独立集合问题

最大子序列和问题2

零钱兑换问题

背包问题

矩阵连乘问题

最优二叉搜索树

最短路径问题

Greedy

活动选择问题

调度问题

Optimal prefix code(最优前缀编码)

编码树

Huffman编码

K-聚类问题

NP

概念

归约（reduction）

基本思想

归约的具体过程

归约的应用

归约的例子

1. TSP（旅行商问题）归约到哈密尔顿回路问题

2. 3SAT 归约到独立集问题

归约的分类

问题

SAT(可满足性问题)——NPC

Vertex cover(顶点覆盖)——NPC

Donimatiing set(支配集)——NPC

Hamiltonian curcuit——NPC

TSP(旅行商问题)

Approximation-近似算法

概念

近似比

PTAS

最小化工时调度问题

一维装箱问题

0-1背包

K聚类问题2

Greedy-2r算法

Greedy-Kcenter算法

聚类问题最优近似比

Local search-局部搜索

问题

顶点覆盖问题

Hopfield神经网络的稳定构型

最大割问题

random algorithm

parallel algorithm-并行算法

PRAM（parallel random access machine）模型

根据内存访问类型分类

WD（work depth）

求和问题

前缀和问题

合并非递减数组问题

解法

寻找数组中最大值问题

External sorting

多路合并

缓存并行处理