【算法】算法设计与分析期末复习总结

第一章算法概述

时间复杂度比大小，用代入法，代入2即可。
求渐进表达式，就是求极限，以极限为O的括号；
O是指上界，Ω是指下界，θ是指上下界相等，在这里，可以这样理解：

f(n) = O(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 大；
f(n) = Ω(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 小；
f(n) = θ(g(n)) 意味着 g(n) 在 n 趋近于无穷大时和 f(n) 同阶；

第二章递归与分治

主定理要掌握，选择题必考：

填空有一道二分搜索，掌握简单版和改进版即可：

#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, m, a[N], x;int bisearch(int x, int a[], int left, int right) {if (left > right)return -1;int middle = (left + right) / 2;if (a[middle] == x)return middle;else if (a[middle] < x)return bisearch(x, a, left, middle - 1);elsereturn bisearch(x, a, middle + 1, right);
}int main() {cin >> n >> m;for (int i = 0; i < n; i++)cin >> a[i];while (m--) {cin >> x;cout << bisearch(x, a, 0, n - 1) <<endl;}return 0;
}

#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, m, a[N], x;pair<int, int> bs(int x, int a[], int left, int right) {if (left > right) {pair<int, int> p(right, left);return p;}int middle = (left + right) / 2;if (a[middle] == x) {pair<int, int> p(middle, middle);return p;}else if (a[middle] < x)return bs(x, a, middle + 1, right);elsereturn bs(x, a, left, middle - 1);
} int main() {cin >> n >> m;for (int i = 0; i < n; i++)cin >> a[i];while (m--) {cin >> x;pair<int, int> p = bs(x, a, 0, n - 1);cout << p.first << " " << p.second << endl;}return 0;
}

接着是排序，快速排序和归并排序的平均时间复杂度都为O(n logn)，快排在最坏情况下的时间复杂度是O(n^2)。

知道中位数概念，一组个数为n的数中，当下标k = (n + 1) / 2时，称为找中位数。

归并的趟数是 logn ，归并的复杂度是 O(n logn)。

第三章动态规划

两个特征，最优子结构和重叠子问题，后者是动态规划和分治法的区别，分治法的子问题是相互独立的，而动态规划的子问题是有重叠的。

0-1背包问题

题目

给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:

共有n+1行输入：
第一行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:

输出装入背包中物品的最大总价值。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

思路

假如现在有五个物品要选，这五个按顺序排下来，从第一个到第五个的最佳选择方案，相当于下面两种的择优选择：

不选第一个+后四个的最佳选择方案；
选第一个+后四个的最佳选择方案；

所以我们发现这是一个具有最优子结构性质的题目，同时也有重合子问题，于是我们可以用动态规划的方法来做。

作为动态规划，我们要严格按照三步走的格式来做：

首先，状态表示，我们设置一个二维数组m[i][j]，作为从第i个到最后一个的最佳选择，同时剩余容量为j；

接着，递归方程，m[i][j] = max ( m[i + 1][j] , m[i + 1][j - w[i]] + v[i] )，也就是从不加第i个的，和加了第i个的这两个方案里选一个总价值最大的；

最后，边界条件，当我们的i为最后一个时，也就是i = n，此时容量从0到最大都可以进行赋值，也就是m[n][j] 的赋值，如果最后一个的重量不比c大，那就设置为这个的价值，如果比c小，就设置为0，注意边界条件在填表时要先写。

现在我们来研究一下最佳方案要怎么打印出来，也就是输出最佳选择组合的各个物品的下标。此时因为dp表已经填完了，所以可以让i从最小开始，我们依次判断即可，怎么判断呢？

直接看物品重量是否不超过剩余重量即可，剩余重量要另起一个变量remain，外层是物品的循环，里面第一重判断是有没有超重，第二重判断是加这个物品是不是比没加要好，把上面max里面的两个照抄即可。

都满足条件，就打印出这个物品的下标，然后使得remain减去这个物品的重量。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 100;int n, c;
int w[N], v[N];
int m[N][N];void dp() {for (int j = 0; j <= c; j++) {if (j >= w[n])m[n][j] = v[n];elsem[n][j] = 0;}for (int i = n; i >= 1; i--) {for (int j = 0; j <= c; j++) {if (j >= w[i])m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);elsem[i][j] = m[i + 1][j];}}cout << m[1][c];
}void print() {int remain = c;for (int i = 1; i <= n; i++) {if (remain >= w[i]) {if (m[i + 1][remain] < m[i + 1][remain - w[i]] + v[i]) {cout << i << ' ';remain -= w[i];}}}cout << endl;
}int main() {cin >> n >> c;for (int i = 1; i <= n; i++)cin >> w[i] >> v[i];dp();print();return 0;
}

第四章贪心算法

选择当前看来最好的方案，这个的题目实在太简单了，不写思路。

题目

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入格式:

共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出格式:

输出为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入样例:

10
56 12 1 99 1000 234 33 55 99 812

输出样例:

291.90

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1010;
int n;
int t[N];int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> t[i];sort(t + 1, t + n + 1);int total = 0;int wait = t[1];for (int i = 2; i <= n; i++) {total += wait;wait += t[i];}cout << fixed << setprecision(2) << 1.0 * total / n;return 0;
}

第五章回溯法

子集和问题

题目

设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法，并输出利用回溯法在搜索树（按输入顺序建立）中找到的第一个解。

输入格式:

输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。
是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出格式:

输出利用回溯法找到的第一个解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。

输入样例:

在这里给出一组输入。例如：

5 10
2 2 6 5 4

输出样例:

在这里给出相应的输出。例如：

2 2 6

思路

这道题是在一堆数里面选择出一组加起来等于目标数的，用回溯法来做就是画出一棵二叉树，每一层树枝代表一个数字，如果选了这个数字，就顺着左子树往下走，没选就顺着右子树往下走，直到最底下，每次选择与否都要记录下来，还得记录当前的数字之和，如果走到叶子时数字之和等于目标数，就可以输出这组数了。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1000;int n, c; // 数字个数，目标数 
int a[N], x[N]; //保存数字的数组，表示数字被选与否状态的数组
int sum = 0, remain = 0; //当前已选数字之和，当前剩余数字之和void backtrack(int t) {if (t > n) {if (sum == c) {for (int i = 1; i <= n; i++) {if (x[i] == 1) cout << a[i] << " ";}cout << endl;exit(0);}return;}remain -= a[t];if (sum + a[t] <= c) {x[t] = 1;sum += a[t];backtrack(t + 1);sum -= a[t];}if (sum + remain >= c) {x[t] = 0;backtrack(t + 1);}remain += a[t];
} int main() {cin >> n >> c;for (int i = 1; i <= n; i++) {cin >> a[i];remain += a[i];}backtrack(1);cout << "No Solution!" << endl;return 0;
}