渐近性原理与表示符号
算法的性质
算法是解决问题的一种方法或一种过程
- 输入 - 有外部提供的量作为算法的输入
- 输出 - 算法至少产生一个量作为输出
- 确定性 - 算法的每一句指令是清晰无歧义的
- 有限性 - 每条指令的执行次数有限，执行每条指令的时间有限
表示符号
O(n)的定义
渐近上界记号
O(g(n))={f(n)∣存在正常数c和n0使得对所有n≥n0有:0≤f(n)≤cg(n)}
试图用一条渐近线g(n)逼近f(n)的上界
Ω的定义
渐近下界记号
Ω(g(n))={f(n)∣存在正常数c和n0,使得对所有的n≥n0,有0≤cg(n)≤f(n)}
Θ的定义
紧渐近界记号
Θ(g(n))={f(n)∣存在正常数c1,c2和n0,使得对所有的n≥n0,有c1g(n)≤f(n)≤c2g(n)}
o的定义
非紧上界符号
o(g(n))={f(n)∣对任何正常数c>0,存在正常数n0,对所有的n≥n0,有0≤f(n)<c(g(n))}
ω的定义
非紧下界符号
ω(g(n))={f(n)∣对任何正常数c>0,存在正常数n0,对所有的n≥n0,有0≤c(g(n))<f(n)}
递归方程渐近阶的求解
代入法
猜上限，用数学归纳法证明正确性
迭代法
公式法
对一个n的问题，划分为大小为bn个子问题，需要求解出其中的a个，合并子问题耗时cnk那么有T(n)={c,aT(bn)+cnk,n=1n≥1
T(n)=⎩⎨⎧O(nlogba)O(nklogbn)O(nk)a>bka=bka<bk
母函数法
常系数线性递归关系
不带有特解的关系
带有特解的关系
看成是通解+特解的形式，先求出通解，然后将特解带入求出特解中未知值，最后得到求解式
第二章 分治法
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int binarySort(int list[], int target, int left, int right) {
while (left <= right) {
int mid = (left + right) / 2;
if (target == list[mid]) {
return mid;
}
else if (target < list[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
|
时间复杂度为O(logn)
归并排序
稳定排序
时间复杂度为O(nlogn)
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| void merge(vector<int> &sortList,int left,int mid,int right) {
vector<int> tempList(right - left + 1);
int leftPos = left;
int rightPos = mid + 1;
int tempPos = 0;
while(leftPos <= mid && rightPos <= right) {
if(sortList[leftPos] < sortList[rightPos]) {
tempList[tempPos++] = sortList[leftPos++];
} else {
tempList[tempPos++] = sortList[rightPos++];
}
}
while(leftPos <= mid){
tempList[tempPos++] = sortList[leftPos++];
}
while(rightPos <= right){
tempList[tempPos++] = sortList[rightPos++];
}
memcpy(&sortList[left],&tempList[0],sizeof(int) * tempPos);
}
void sortNonRecursive(vector<int> &sortList) {
if (sortList.empty() || sortList.size() <= 1) {
return;
}
for (int i = 1; i < sortList.size(); i *= 2) {
int left = 0;
int mid = left + i - 1;
int right = mid + i;
while (right < sortList.size()) {
merge(sortList, left, mid, right);
left = right + 1;
mid = left + i - 1;
right = mid + i;
}
if (left < sortList.size() && mid < sortList.size()) {
merge(sortList, left, mid, sortList.size() - 1);
}
}
return;
}
void sortRecursive(vector<int> &sortList, int left, int right) {
if (sortList.empty() || sortList.size() <= 1) {
return;
}
if (left < right) {
int mid = (left + right) / 2;
sortRecursive(sortList,left,mid);
sortRecursive(sortList,mid+1,right);
merge(sortList, left,mid,right);
}
}
|
快排
不稳定排序
时间复杂度为O(nlogn)→O(n2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int partition(int list[],int left,int right) {
int begin = left;
while(left < right) {
while(left < right && list[right] >= list[begin]) {
right--;
}
while(left < right && list[left] <= list[begin]) {
left++;
}
swap(list[left],list[right]);
}
swap(list[begin],list[left]);
return left;
}
void quickSort(int list[],int left,int right) {
if(left >= right) {
return;
}
int midPos = partition(list,left,right);
quickSort(list,left,midPos - 1);
quickSort(list,midPos + 1,right);
}
|
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
|
int partition(vector<int> &sortList,int left,int right) {
int leftPos = left;
int rightPos = right;
int midValue = sortList[leftPos];
while(left < right) {
while(left < right && sortList[rightPos] > midValue) {
rightPos--;
}
if(left < right) {
sortList[leftPos++] = sortList[rightPos];
}
while(left < right && sortList[leftPos] < midValue) {
leftPos++;
}
if(left < right) {
sortList[rightPos--] = sortList[leftPos];
}
}
sortList[leftPos] = midValue;
return leftPos;
}
void quickSort(vector<int> &sortList,int left,int right) {
if(sortList.size() <= 1) {
return;
}
int leftPos = partition(sortList,left,right);
quickSort(sortList,left,leftPos - 1);
quickSort(sortList,leftPos + 1,right);
}
void randomSelect(vector<int> &sortList,int left,int right) {
int midPos = rand() % (right - left) + left;
swap(&sortList[left],&sortList[midPos]);
return partition(sortList,left,right);
}
|
快排之所以不稳定，是因为在左右指针移动并交换对应位置元素时，有可能将两个相同元素互换位置。解决方法是可以创建一个临时数组，将交换的元素放到临时数组中，最后将临时数组放回原数组。
快排最好的情况是每次基准值都为中位数，此时相当于归并排序的分解阶段
快排最坏的情况是每次基准值的一边没有其他数字，此时算法退化为一般的排序
T(n)=⎩⎨⎧O(1)2T(2n)+O(n)=O(nlogn)O(n2)n=1n>1最好n>1最坏
线性时间选择
在n个元素中找到第k小的元素
需要使得时间复杂度为O(n)
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
|
int select(vector<int> list,int left,int right,int target) {
if(right - left < 75) {
sort(list);
return list[left + target - 1];
}
for(int i = 0;i <= (right - left - 4) / 5;i++) {
swap(&list[p+5*i + 2],&list[p+i])
}
int middle = select(list,left,left + (right - left - 4) / 5,(right - left - 4) / 5 / 2)
int middlePos = partition(list,left,right,middle);
if(target == middlePos) {
return list[target];
} else if (target < middlePos) {
vector<int> child = (list.begin(),list.begin() + middlePos)
return select(child,target);
} else {
vector<int> child = (list.begin() + middlePos + 1,list.end())
return select(child,target - middlePos - 1);
}
}
|
T(n)={C1C2n+T(5n)+T(43n)=O(n)n<75n≥75
5就是按每5个划分为一组
设所有元素互不相同，此时每次找出的基准x至少比103(n−5)个元素大，因为每一组有2个元素小于本组中位数，n/5个中位数又有10(n−5)个小于基准x。同理，此时基准x至少比103(n−5)个元素小。故当n≥75，103(n−5)≥4n，也就是说这样划分得到的两个子数组的长度都至少缩短四分之一
平面最接近点对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| double getDistance(pointList) {
int pointNum = pointList.size;
if(pointNum == 2) {
return Dist(pointList);
}
int median = pointList中各个点的x坐标的中位数
vector<point> S1 = {p.x <= median}
vector<point> S2 = {p.x > median}
distance1 = getDistance(S1);
distance2 = getDistance(S2);
distanceMin = min(distance1,distance2);
vector<point> P1 = {abs(p.x - median) <= distanceMin && p in S1}
vector<point> P2 = {abs(p.x - median) <= distanceMin && p in S2}
P1S,P2S = sort(P1+P2,p.y)
distanceMinB = 区间内得到的最小距离
return min(distanceMin,distanceMinB)
}
|
在分治前先对list中所有点按y坐标预排序，这样将p1,p2中各点按y坐标值排序(投影排序) 的操作可以优化为O(n)，那么最后的时间复杂度为
T(n)={O(1)2T(2n)+O(n)=O(nlogn)n<4n≥4
第三章 动态规划
最长子序列
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
45
46
47
48
49
50
| #include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
void LCS(int i,int j,vector<char> x,vector<vector<int> > b) {
if(i==0 || j==0) {
return;
}
if(b[i][j]==1) {
LCS(i-1,j-1,x,b);
cout<<x[i - 1] << " ";
} else if (b[i][j]==2) {
LCS(i-1,j,x,b);
} else {
LCS(i,j-1,x,b);
}
}
int LCSLength(vector<char> &A, vector<char> &B) {
int c[A.size() + 1][B.size() + 1];
vector<vector<int> > b(A.size() + 1,vector<int>(B.size() + 1, 0 ));
for (int i = 0; i <= A.size(); i++) {
c[i][0] = 0;
}
for (int i = 0; i <= B.size(); i++) {
c[0][i] = 0;
}
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
} else if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
b[i][j] = 2;
} else {
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
LCS(A.size(),B.size(),A,b);
return c[A.size()][B.size()];
}
|
c[i][j]=⎩⎨⎧0c[i−1][j−1]+1Max(c[i−1][j],c[i][j−1])i=0,j=0A[i]=B[j]A[i]=B[j]
长度矩阵c[i][j]表示A[0]A[i]与B[0]B[j]的最长子序列长度
算法的时间复杂度为
T(n)=O(MN)M、N是两条序列的长度
当然，还可以将长度矩阵c优化为两行的循环数组，因为c每次只从上一行和上一列取值
当然，如果不需要输出子序列，就直接干掉b省空间，或者不需要b，通过直接判断当前i、j对应的c[i][j]所对应的状态来输出子序列的元素
最长上升/下降子序列
要求一个序列的最长上升/下降子序列，可以利用最长公共子序列的思想
将原序列A复制一份为序列B，将序列B进行正序/倒序排序，然后求A、B的最长公共子序列即为A的最长上升/下降子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int main() {
vector<char> a;
vector<char> b;
int aNum;
cin >> aNum;
for (int i = 0; i < aNum; i++) {
char temp;
cin >> temp;
a.push_back(temp);
}
b = a;
sort(b.begin(),b.end(),[](char x,char y){return x > y;});
cout << LCSLength(a, b) << endl;
return 0;
}
|
回文词构造问题
回文词的构造问题描述
• 对于任意给定的一个字符串(由大写字母、小写字母和数字字符构成)，都可以通过插入若干个字符的方法将其变成一个回文串。
• 例如:给定一个字符串Ab3bd，在插入两个字 符后就可以变成一个回文串，如可以在A的左边添上一个d，再在最后一个d之前添上一个A， 这样改造后的字符串为dAb3bAd，它是一个回文串。
• 那么对于任意给定的一个字符串，最少要插入几个字符才能将其变成回文串呢?
解题思路与上题相同，区别在于复制A为B，再将B倒序，然后应用LCS
得到的最长子序列长度为n，那么需要再插入A.length() - n个字符，就能变成回文串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int main() {
vector<char> a;
vector<char> b;
int aNum;
cin >> aNum;
for (int i = 0; i < aNum; i++) {
char temp;
cin >> temp;
a.push_back(temp);
}
b = a;
reverse(b.begin(),b.end());
cout << aNum - LCSLength(a, b) << endl;
return 0;
}
|
最大子段和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int getMaxSum(int list[],int listNum) {
int maxSum = 0;
int b[listNum];
for(int i = 1;i <= listNum; i++) {
if(b[i-1] > 0) {
b[i] = b[i-1] + list[i];
} else {
b[i] = list[i];
}
if(b[i] > maxSum) {
maxSum = b[i];
}
}
return maxSum;
}
|
动态规划递归式为
b[i]=Max{b[i−1]+A[i],A[i]}1≤i≤n
实际上，b数组可以只由一个变量代替
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int getMaxSum(int list[],int listNum) {
int maxSum = 0;
int sum = 0;
for(int i = 1;i <= listNum; i++) {
if(sum > 0) {
sum += list[i];
} else {
sum = list[i];
}
if(sum > maxSum) {
maxSum = sum;
}
}
return maxSum;
}
|
如果要记录最长子段的起点和终点，并且要求起点和终点尽可能靠前，那么可以从后往前循环，这样最后起点和终点坐标会因此靠前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int getMaxSum(vector<int> list) {
int maxSum = 0;
int sum = list[list.size() - 1];
int tempEnd = list.size() - 1;
int begin = list.size() - 1;
int end = list.size() - 1;
for(int i = list.size() - 2;i >= 0 ;i--) {
if(sum > 0) {
sum += list[i];
} else {
sum = list[i];
tempEnd = i;
}
if(sum >= maxSum) {
maxSum = sum;
end = tempEnd;
begin = i;
}
}
cout << "begin:" << begin << " end:" << end << endl;
return maxSum;
}
|
两段最长子段和
找一个数组中两段的子段和使其最大
使用求最大子段和的方法，求以下变量
1
2
3
4
5
| dpA[i]
maxA[i]
dpB[i]
maxB[i]
|
然后，通过循环i依次比较以下的数值得到最大和
1
2
| i = 0～n-2
maxSum = max(maxA[i] + maxB[i+1]);
|
完整代码如下：
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
| int maxA[MAXN],maxB[MAXN]
int getMaxSum(int list[],int n) {
int dp = 0;
maxA[0] = dp = list[0];
for(int i = 1;i < n;i++) {
if(dp > 0) {
dp += list[i];
} else {
dp = list[i];
}
if(dp > maxA[i-1]) {
maxA[i] = dp;
} else {
maxA[i] = maxA[i-1];
}
}
int dp = 0;
maxB[n-1] = dp = list[n-1];
for(int i = n-2;i >=0;i--) {
if(dp > 0) {
dp += list[i];
} else {
dp = list[i];
}
if(dp > maxB[i-1]) {
maxB[i] = dp;
} else {
maxB[i] = maxB[i-1];
}
}
int Max = maxA[0] + maxB[1];
for(int i = 1;i < n-1;i++) {
if(Max < maxA[i] + maxB[i+1]) {
Max = maxA[i] + maxB[i+1];
}
}
return Max;
}
|
0-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
动态规划递归表达式为
m(i,j)={max{m(i−1,j),m(i−1,j−wi)+vi}m(i−1,j)wi≤j0≤j<wim(i,j)表示下标为0～i的物品中，不超过容量j的最优值0<i≤n0<j≤C
初始化表达式为
m(0,j)={0v0j<w0w0≤j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int getBag(int num,int volume,int goodCapacity[],int goodValue[]) {
int dp[num][volume+1];
for (int j = 0; j < volume + 1 ;j++) {
dp[0][j] = (goodCapacity[0] <= volume) ? goodValue[0] : 0;
}
for (int i = 1;i < num;i ++) {
for(int j = 0;j < volume + 1;j++) {
dp[i][j] = max(dp[i-1][j],
(goodCapacity[i] <= j)
? dp[i-1][j-goodCapacity[i]] + goodValue[i]
: 0);
}
}
return dp[num - 1][volume];
}
|
如果要输出最佳搭配，可以通过设置一个记录数组，分情况记录选择
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
| int getBag(int num,int volume,int goodCapacity[],int goodValue[]) {
int dp[num][volume+1];
bool select[num][volume+1];
for (int i = 0; i < volume + 1 ;i++) {
if(goodCapacity[0] <= i) {
dp[0][i] = goodValue[0];
select[0][i] = true;
} else {
dp[0][i] = 0;
}
}
for (int i = 1;i < num;i ++) {
for(int j = 0;j < volume + 1;j++) {
if(goodCapacity[i] <= j) {
if(dp[i-1][j] > dp[i-1][j-goodCapacity[i]] + goodValue[i]) {
dp[i][j] = dp[i-1][j];
select[i][j] = false;
} else {
dp[i][j] = dp[i-1][j-goodCapacity[i]] + goodValue[i];
select[i][j] = true;
}
} else {
dp[i][j] = max(dp[i-1][j],0);
select[i][j] = false;
}
}
}
for (int i = num - 1,j = volume;i >= 0 && j>=0;i--) {
if(select[i][j]) {
cout << i << " ";
j -= goodCapacity[i];
}
}
return dp[num - 1][volume];
}
|
需要注意的是，输出的结果是背包的下标
并且，以倒序输出
