算法期末复习

算法期末复习

算法基础

插入排序

https://jasonxqh.github.io/2020/08/28/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%92%8C%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/

分治法

渐近符号

https://blog.csdn.net/so_geili/article/details/53353593

渐近紧确界记号 $\Theta$

渐近上界记号:$O$

渐近下界记号:$\Omega$

非渐近紧确上界:$o$

小o和大O的区别就在于:

$O(n^2)$可以是 n,2n,1,$2n^2$等,但是$o(n^2)$ 可以是 n,1,3n等,但不能是 $n^2$ ,是 小于号的关系

非渐近紧确下界:$\omega$

和o与O的关系一样。$ω(n^2)$可以是$n^3,n^{10}$等,但不能是$n^2$。$Ω(n^2)$可以是$n^2,n^3$,$n^{10}$等。

分治策略*

矩阵乘法 Strassen

代入法求解递归式

递归树方法求解递归式

主方法求解递归式

堆排序

https://jasonxqh.github.io/2020/05/07/%E5%A0%86%E6%8E%92%E5%BA%8F/

快速排序

https://jasonxqh.github.io/2020/05/06/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/

线性时间排序*

排序算法的下界

记数排序与基数排序

中位数和顺序统计量*

期望为线性的时间

最坏为线性的时间

散列表

散列表

https://jasonxqh.github.io/2020/05/09/hashtable/

开放寻址法

线性探查

给定一个普通的散列函数 h',称之为辅助散列函数,线性探查采用的散列函数为: $h(k,i)=(h’(k)+i)\mod~m$

二次探查

二次探查采用这种散列函数 $h(k,i)=(h’(k)+c_1i+c_2i^2)\mod m$

其中 $h’$ 是一个辅助散列函数,$c_1,c_2$为正的辅助常数

双重散列

双重散列是用于开放寻址法最好的方法之一,因为它所产生的排列具有随机选择排列的许多特性。双重散列采用如喜爱形式的散列函数

$h(k,i)=(h_1(k)+ih_2(k)) \mod m$

二叉搜索树

https://jasonxqh.github.io/2020/06/17/BSTandAVL/

概念

查询、插入、删除

红黑树

https://jasonxqh.github.io/2020/11/03/%E7%BA%A2%E9%BB%91%E6%A0%91/

性质、旋转、插入

动态规划

原理

钢条切割

矩阵链乘法

https://jasonxqh.github.io/2020/11/17/%E7%9F%A9%E9%98%B5%E9%93%BE%E4%B9%98%E6%B3%95/

贪心算法

原理

活动选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int maxn=1500;
struct node
{
int beginTime;
int endTime;
node()
{
beginTime=0;
endTime=0;
}
}a[maxn];

bool cmp(node a,node b)
{
if(a.endTime!=b.endTime) /*如果两个活动的结束时间不相等*/
return a.endTime<b.endTime;
if(a.endTime==b.endTime)
return a.beginTime<b.beginTime;
}

int main()
{
int n,i;
cin>>n;
for(i=1; i<=n; i++)
{
cin>>a[i].beginTime>>a[i].endTime;
}
sort(a+1,a+1+n,cmp);//按照结束时间从早到晚开始排队
int cnt=0;
int tmp=-1;/*用于进行贪心选择的变量*/
for(i=1; i<=n; i++)/*进行活动选择 */
{
if(a[i].beginTime >= tmp)
{
tmp=a[i].endTime;
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}

赫夫曼编码

哈夫曼编码

摊还分析*

聚合分析

核算法

势能法

动态表

图算法

图的表示

广度优先

https://jasonxqh.github.io/2020/08/30/BFSandDFS/

深度优先

https://jasonxqh.github.io/2020/08/30/BFSandDFS/

最小生成树

最小生成树的形成

Kruskal和Prim

https://jasonxqh.github.io/2020/06/21/%E5%9B%BE%E4%B8%8E%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/

单源最短路径

Dijkstra算法

https://jasonxqh.github.io/2020/06/21/%E5%9B%BE%E4%B8%8E%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/

最大流

流网络

Ford-fulkerson方法

NP完全性

多项式时间、多项式时间的验证

NP完全性与可规约性

典型的NP完全问题

团问题、顶点覆盖问题、哈密顿回路问题等

近似算法

顶点覆盖问题

旅行商问题

集合覆盖问题

-------------本文结束,感谢您的阅读-------------