算法考试复习

2020-02-17 本文已影响0人 FakeCSer爱去网吧

引论

算法与数据结构与程序的区别
- 算法是求解问题的过程描述：从蛮力到策略
- 数据结构是数据的组织与存储：从杂乱无章到井然有序
- 程序 = 算法 + 数据结构
算法描述
- 自然语言
- 伪代码
- 流程图
三种不同的计算机问题
- 判断问题（yes,no）例如输入的数是否大于60
- 优化问题（求最优解）例如从A到B的最短路径是什么
- 数值计算
常见的计算机问题
- 排序
- 查找
- 串处理
- 图问题
- 组合问题
- 几何问题
- 数值问题
概念
- 什么是算法：算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
- 算法特征
  - 输入：算法有零个或多个输入量
  - 输出：算法至少产生一个输入量
  - 确定性：没有二义性
  - 有穷性：有限步后结束
- 要点：
  - 算法的每一个步骤必须清晰、明确
  - 算法所处理的输入的值域必须仔细定义。
  - 同样的一个算法可以用几种不同的形式来描述
  - 可能存在几种解决相同问题的算法
  - 针对同一个问题的算法可能会基于完全不同的解题思路

算法复杂性分析

算法的时间效率和空间效率度量都用输入规模的函数来度量
时间复杂度：

T(n) ≈ copC(n)

n是该算法的输入规模

cop是特定计算机上一个算法基本操作的执行时间（基本操作：最内层循环操作）

C(n)是该算法需要执行的基本操作的次数
- 最优效率，最差效率，平均效率
- 指数级复杂度与多项式级复杂度
  - 指数级复杂度：很多穷举搜索，但要尽量避免，只能用于规模很小的问题
  - 多项式算法
- 渐进表达式：忽略常数
  - O（读"O"）:上界
  - Ω（读"omiga"）:下界
  - Θ（读"theta"）：近似

若f(n)=32n^2+17n+32，和O(n),Ω (n), Θ(n), O(n^2), Ω(n^2), Θ(n^2),O(n3), Ω(n^3), Θ(n^3).相匹配

则f(n)属于O(n^2)、O(n3)、Ω(n^2)、Ω (n)、Θ(n^2)

理解：以O(n^{2)为例，O(n}2)表示一个集合，表示所有比kn^{2小的函数(k为任意正常数)，或者函数图像在kn}2下方的函数，所以f(n)∈O(n^2)表示32n2+17n+32也是属于此集合。
注意
- O(n^2)表示一个集合
- 所以用等号时等价于属于符号：f(n)=O(n^{2)等价于f(n)∈O(n}2)
- 更加方便理解的式子

f(n)= O(g(n)) 理解为 f(n) ≤ kg(n);
f(n)= Ω(g(n)) 理解为 f(n) ≥ kg(n);
f(n)= Θ(g(n)) 理解为 f(n) = kg(n);
f(n)= o(g(n)) 理解为 f(n) < kg(n);
f(n)= ω(g(n)) 理解为 f(n) > kg(n).

基本的效率类型

c < logn < (logn)^2 < n < nlogn < n^2 < n^3 < 2^n < n!

n：找n个数最大值

nlogn多出现在分治算法中：如合并排序和堆排序

n^2：平面上多点求最近两点之间距离时每对点尝试

n^k：多项式时间：如独立集问题

指数时间：最大独立集问题
渐进增长率比较的方法
- 极限法
  
  相除取极限，=0，=c，=∞
- 取对数再比较

贪心算法

思想：每步最优
硬币零钱问题 (coin changing)

对于某些指定硬币面值类型，使用贪心策略（优先最大面值）可以求得最小硬币数来组成某数。例如我国的货币面值类型（1元，5元，十元，50元，100元），或（1,5,10,25,100）

证明：此时贪心算法是求得的解最优解：

以(1,5,10,25,100)为例

思路：首先明显有性质:

N1（1元的数量）≤4   //大于4可用一个5来代替，结果更优
N5≤2
N10+N25≤2
N25≤3

对于求总额x的零钱策略：有ck ≤ x ≤ ck+1。则依照贪心策略，必须取ck。若存在非贪心最优解，则不取ck，此时就必须在c1,...ck-1中选择硬币来代替ck，则会与上述性质矛盾

贪心算法不是对所有的硬币问题都适用
任务安排问题 (interval scheduling )

寻找不重叠的最多任务数。

策略：以结束时间排序，后贪心选择不重叠最早的结束的一个任务。

证明：此时贪心算法是求得的解最优解：

假设俩个解，

一个是最优解（任务i1...ir,x，j1...jm）

一个是贪心解 (任务i1...ir,y，q1...qn）

即
- 前r个任务选择相同
- x任务比y任务结束时间晚，但是m>n（最优解数量大于贪心解数量）
则x一定可以换为y,（上一个任务相同，x任务比y任务结束时间晚，可画图来解释），所以最优解一定可以转换为贪心解，即贪心解是最优解。
课程分配教室问题(interval partitioning)

给有不同开始结束时间的课程分教室，使得教室数最少

策略，每次贪心给一个教室最早开始时间的课程
多任务最早结束问题

每个任务有开始结束时间，问所有任务最晚结束的时间

策略：最早结束时间排序

分治

思想：分而治之
步骤
1. 将问题划分为若干个子问题(同样规模)
2. 递归求解每个子问题，注意写好递归边界
3. 将若干子问题的解合并成问题的解
时间复杂度nlogn
逆序对

问题：给定一个序列，例如a[5]={5,4,8,10,2}，找出这样的数对，i<j,a[i]>a[j]例如这个例子包含(5,4),(5,2),(4,2),(8,2),(10,2) 5个逆序对。

策略：
1. 分两段A,B，分别求A，B中逆序数,N1,N2。T(n)+T(n)
2. 求a∈A，b∈B的逆序数，N3
  
  N3=0;
  
  比较ai,bj,(ai∈A，bj∈B)
  
  若ai小，ai入数组C，i+1
  
  若bj小，bj入数组C，j+1。N3+=A中剩余的数的个数。Θ(n)
  
  在归并排序的同时记录一个数据。
3. 加起来,N1+N2+N3。
有递推式：

T（n）={
Θ(1) if n=1
2T(n/2)+Θ(n) if n>1
}

主定理（master theorem ）

根据递推式来确定时间复杂度

p1.png
整数乘法（ integer multiplication ）

问题描述：

x=10001101,y=11100001,计算x*y

以x和y的位数做输入规模n，常规计算方法并不是最优Θ(n^2)

策略:

分治思想,x=10001101,y=11100001

将x和y分成前4位和后四位。

m= ⎡n/2⎤ (x,y有n位)

a = ⎣x/2^m⎦ , b = x mod 2^m

c = ⎣y/2^m⎦ ,d = y mod 2m

即a=1000,b=1101,c=1110,d=0001

利用交换律：有以下公式

xy=(2^m*a+b)(2m*c+d)=2/^2mac+2m(bc+ad)+bd

所以将x*y转换成了四次规模为原来一半的乘法

有

T（n）={
Θ(1) if n=1
4T(n/2)+Θ(n) if n>1
}

根据主定理

T(n) = Θ(n^2)所以并没有提升效率

所以但是可以观察出若求得小规模的乘法数量小于4，就会提升效率，所以将公式变形

xy=(2^m*a+b)(2^m*c+d)=2/^2mac+2^m(bc+ad)+bd
                    = 2^2m*ac+2^m(ac+bd–(a–b)(c–d))+bd

此时只有个规模更小的运算

所以

T（n）={
       Θ(1)            if n=1
       3T(n/2)+Θ(n)    if n>1
       }

则T(n) = Θ(n^log3)=O(n1.585)

矩阵乘法（matrix multiplication）

常用计算时间复杂度为Θ(n^3)

分治，经过一系列公式推导有

T(n) = 7T(n/2)+Θ(n^2) = =Θ(n^log7)=O(n2.81)
最近点对（closest pair of points ）

问题描述：

给定平面上n个点，求这n个点中距离最近的两个点的距离是多少。

策略：我们将平面上的点划分为两部分，每部分n/2个点,递归求解两部分的最近点距离。难点在于子问题的合并：求出两小部分中的最近点d1,d2后，将两小部分合成一个大部分时，大部分的最近点问题（两个点来自不同的部分d3），则此时大部分最进点对距离min{d1,d2,d3}。
- 如何寻找d3：
  - 记min{d1,d2}=δ
  - 找到距离两小部分边界小于δ的点（在横坐标区域[-δ，δ]内）
  - 计算区域内的最小距离即为d3

动态规划

重叠子问题，最优子结构

带权任务安排问题：weighted interval scheduling

此时贪心算法并不能得到最优解

策略：
1. 以结束时间排序 f1<f2<...<fn
2. p(j)上一个与任务j相容的任务
3. OPT(j)表示j前任务（1-j）相容子集最大权重，所以目标是OPT(n)
所以对于求OPT(j)，根据是否选择j有公式

OPT(j)={
  0                                 if j=0
  max{OPT(j-1),wj+OPT(p(j))}        if j>0
}

矩阵连乘问题
最长公共子序列

OPT(i,j)={
    o                        if i=0||j=0
    OPT(i,j)=1               if i,j>0,xi=yj
    max{OPT(i,j-1),c(i-1,j)}  if i,j>0,xi!=yj
}

01背包问题

对于i号物体有重量wi和价值vi,求总量W最多能装多少价值的东西

策略：

OPT(i,w)表示放前i个物体后，剩下的空间
- 根据是否选择i号物体有公式

OPT(i,w)={
  0                                 if i=0
  OPT(i-1,w)                        if wi>w
  max{OPT(i-1,w),vi+OPT(i-1,w-wi)}  otherwise
}

P,NP,NPC,NPhard

https://blog.csdn.net/sinat_21591675/article/details/86521190 一个很好的讲解博客

规约

X规约到Y——X可由 标准多项式次数 加 多项式次数的调用Y 组成

规约是将一个特殊问题一般化的过程。

X ≤ p Y.

If X ≤ P Y and Y can be solved in polynomial time, then X can be solved in polynomial time.

If X ≤ P Y and Y can be solved in polynomial time, then X can be solved in polynomial time.

y 比 x 难

P

多项式时间里解决的判定问题
NP

多项式的时间里验证一个解，不确定是否能在多项式时间求解
P ⊆ NP ⊆ EXP
P=NP？即是否多项式验证就可多项式求解
NPC

NP完全问题，最难的NP问题：所有的NP问题都可以归约到的一个NP问题。

NPC的证明：If X ∈ NP-complete, Y ∈ NP, and X ≤ p Y, then Y ∈ NP-complete.

Basic genres of NP-complete problems and paradigmatic examples.
- Packing/covering problems: SET-COVER, VERTEX-COVER,INDEPENDENT-SET.
- Constraint satisfaction problems: CIRCUIT-SAT, SAT, 3-SAT.
- Sequencing problems: HAMILTON-CYCLE, TSP.
- Partitioning problems: 3D-MATCHING, 3-COLOR.
- Numerical problems: SUBSET-SUM, KNAPSACK.

如果p!=np 则难度

P<NP<NPC<NP-hard

如果p=np 则难度

P=NP=NPC 属于NP hard的一个子集

一线
- 点独立集和点覆盖集
  - 点覆盖集：一个点集合：图中所有边与此集合中某点邻接
  - 电独立集：一个点集合：此集合中任意两点之间没有边相连
  INDEPENDENT-SET ≡ p VERTEX-COVER.
  
  此两个问题可以相互规约，点覆盖集加点独立集可以合成这张图（互补）
- 点覆盖集规约到集合覆盖
  - 集合覆盖：一个大的集合和若干子集合，求用k个子集合并集可以组成原集合。
  - 点覆盖集：一个点集合：图中所有边与此集合中某点邻接
    
    图中的点---子集合
    
    图中的边---子集合中的元素
  VERTEX-COVER ≤ p SET-COVER.
- 可满足性问题-satisﬁability （SAT）
- 例如公式

 Φ = （x1(反) ∨ x2 ∨ x3 ）∧ （x1 ∨ x2(反) ∨ x3  ) ∧（x1(反) ∨ x2 ∨ x4 ）

是否存在布尔值的xi使公式的结果为ture

  x1 = true, x2 = true, x3 = false, x4 = false

3-SAT意为每个括号有三个元素

- SAT可以规约到独立集问题

  每个括号是一个三角形的图，元素做点，每个三角形之间互反的元素链接

有3-SAT ≤ P INDEPENDENT-SET ≤ P VERTEX-COVER ≤ P SET-COVER.

2线
- 规约和转化
  - 转化：如果给定X的任何一个实例，我们可以构造Y的一个实例y，使得x是X的yes实例，如果Y是Y的yes实例。
  - 转化相当于规约中X只用了一次Y而不是多项式次数的Y。
- 哈密顿环问题（遍历图中所有点的环）
  - 有向图哈密顿环问题归约到哈密顿环问题，将一个点分成三个点来模拟有向性
  - 3-SAT归约到有向图哈密顿环，问题，先根据CETIFEIR构造有向环，左到右为xi=1.后在某两点之间额外构造新连线。来验证是否符合。CETIFEIR
- 3SAT归约到最远路径问题
- 哈密顿环归约到旅行商问题
3线
- 3-SAT归约到3着色问题
- 平面图和地图着色问题相互规约
  
  图中没有两条边相交即称这个图是平面的
  
  平面的图在处理很多问题（最短路径最大流最小割MST等等）上会变容易
  
  平面三着色问题是NPC
- 平面图三着色与普通图三着色
  
  普通三着色归约到平面三着色，普通NPC -推出->平面NPC
- K-着色问题，任何图都是4可着色图
4线
- 3可满足问题归约到子集合和问题
  
  Ex. { 215, 215, 275, 275, 355, 355, 420, 420, 580, 580, 655, 655 },
  
  W = 1505.
  
  Yes. 215 + 355 + 355 + 580 = 1505.
  
  转换到二进制
- 子集合和归约到01背包问题
树的独立集问题
- 不带权：贪心。事实：一定有独立集包含叶子
- 带权：动态规划
最小覆盖集
- 二倍近似，贪心
3-SAT，求法
TSP 动态规划O(n^2 *2^n)

相似算法

负载均衡

贪心每个任务分给当前任务最小的机器，是二倍近似的。证明：考虑一次分配的过程

优化，先将任务降序排列之后用上述贪心1.33倍近似。证明：考虑一次分配的过程
中心选择

将第一个中心放在单个中心的最佳位置，然后继续添加中心，以便每次都尽可能减小覆盖半径。反复选择下一个中心距任何现有中心最远的站点。此算法是二倍近似的
最小带权点覆盖集

出价方式。是二倍近似的

ILP(整数规划) min∑wi*xi nph

LP 可解决 2近似
广义负载均衡

ILP

LP
01背包问题

分界线

图的算法

prim,kruskal求最小代价树
floyd O(N^3)，dijkstra O(N^2)求最短路径