算法导论
插入排序
堆排序
快速排序
随机快速排序
线性时间内排序：Counting sort（计数排序），Radix sort（基数排序），Bucket sort（桶排序）
分治三个步骤：
- 分解步骤将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小
- 解决步骤递归地求解出子问题，如果子问题的规模足够小，则停止递归，直接求解
- 合并步骤将子问题的解组合成原问题的解
动态规划四个步骤：
- 刻画一个最优解的结构特征
- 递归地定义最优解的值
- 计算最优解的值，通常采用自底向上的方法
- 利用计算出的信息构造一个最优解
主定理求递归时间复杂度
\[T(n)=aT(n/b) + f(n)\]- \[if \space f(n)=O(n^{log_{b}{a}-\epsilon})\space for \space some \space constant \space \epsilon>0,then \space T(n)=\Theta(n^{log_{b}{a}})\]
- \[if \space f(n)=\Theta(n^{log_{b}a}log^{k}n)\space with \space k>=0,then \space T(n)=\Theta(n^{log_{b}a}log^{k+1}n)\]
- \(if \space f(n)=\Omega(n^{log_{b}{a}+\epsilon})\space with \space \epsilon > 0, and \space f(n) \space satisfies \space the \space condition, then \space T(n)=\Theta(f(n))\) \(Regularity \space condition:af(n/b)<=cf(n)\space for \space some \space constant \space c < 1 \space and \space all \space sufficiently \space large \space n\)
Partition算法求第i小，最坏n2
最大子数组和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dp[i] 表示以i为最后一项的连续子数组和的最大值
dp[0] = arr[0]
dp[i] = max(dp[i - 1] + arr[i], arr[i])
压缩空间：
for (int i = 0; i < n; i++) {
if (sum < 0) {
sum = arr[i];
} else {
sum += arr[i];
}
ans = max(ans, sum);
}
return ans;
装配线调度
1
2
3
4
dp1[0] = e1 + a[1][0]
dp1[i] = min(dp1[i - 1] + a[1][i], dp2[i - 1] + t[2][i - 1] + a[1][i]) (i >= 1)
dp2[0] = e2 + a[2][0]
dp2[i] = min(dp2[i - 1] + a[2][i], dp1[i - 1] + t[1][i - 1] + a[2][i]) (i >= 1)
矩阵链乘
1
2
3
dp[i][j]表示i到j之间的矩阵乘法次数
dp[i][j] = 0 (i == j)
dp[i][j] = min{dp[i][k] + dp[k + 1][j] + p[i - 1]p[k]p[j]} i <= k <= j (i < j)
最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
dp[i][j]表示x的前i个和y的前j个的最长公共子序列长度
for (int i = 1; i < len(x) + 1; i++) {
for (int j = 1; j < len(y) + 1; j++) {
if x[i - 1] == y[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1];
}
}
}
return dp[len(x)][len(y)];
最长公共子串
1
2
3
4
5
6
7
8
9
10
11
12
13
dp[i][j]表示以x的第i个字符为结尾，以y的第j个字符为结尾的最长公共子串长度
int result = 0;
for (int i = 1; i < len(x) + 1; i++) {
for (int j = 1; j < len(y) + 1; j++) {
if (x[i - 1] == y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
result = max(result, dp[i][j]);
}
}
return result;
活动选择问题 Activity-selection problem
贪心：结束时间升序排列，从前往后能选就选
01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
dp[i][j]表示容量为j装前i个物品的最大价值
for (int i = 1; i <= weights.size(); i++)
{
for (int j = capacity; j >= weights[i - 1]; j--)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
}
}
return dp[weights.size()][capacity];
压缩空间：
for (int i = 0; i < weights.size(); i++)
{
for (int j = capacity; j >= weights[i]; j--)
{
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
分数背包
1
2
value/weight 降序排序
贪心
dijkstra O(E+VlgV)
Bellman Ford O(VE)
Floyd-Warshall
Johnson’s algorithm 为每个结点找一个值做dijkstra
LC检索 Least Cost Search
可计算性：
不可判定问题Undecidable Problem
NP完全问题NP-Complete：SAT，3-color，TSP