算法上课内容总结
LEC 1 概述
解决问题的三要素：输入 输出 算法
数据结构
输入、输出与数据结构直接相关。
数据结构时数据之间的逻辑关系、数据在计算机上的存储方式、数据的操作。
数据结构与算法设计是密切相关的。
算法
算法是为了求解问题而给出的指令序列。
一般特性
正确性
有效性
确定性
有穷性
算法效率
计算时间
存储空间
网络带宽
LEC 2 算法渐进分析
一般我们不必花大力气算出算法的精确运行时间，我们关心的是在大规模的输入下，算法的运行时间是如何随着输入规模的增大而变化的。此时，我们可以忽略低阶项和常量，使用渐进分析。
开销函数的估计是相对的而不是绝对的，开销函数的阶的增长决定了开销的大小。
渐进符号
$O$ 渐进上界
$Ω$ 渐进下界
$Θ$ 渐进紧确界
分析实例
矩阵求和
$O(n)$ $n=k^2$ （k 为矩阵维度）
插入排序
最好 O(n) 最坏 O(n^2)
合并排序
$O(nlgn)$
LEC 3 递归关系
许多算法，时间开销函数都可以用递归关系来描述。
置换法
猜想出一个表达式，验证表达式的正确性。
递归树
将迭代过程展成树的形式，分析树的每一层的消耗，然后求和。
迭代法
根据迭代公式，利用数学方法求解。
主方法
主方法依赖如下的主定理：
可以根据主定理方便求解效率，但有真空地带。
LEC 4 线性时间的排序法
基于比较的排序的开销下限
这一节先分析了基于比较的方法的排序的开销下限，我们通过判定树模型证明下限为$nlgn$。要打破这个下限，就要寻找非比较的排序方法，即：
计数排序
基本思想是排序指定范围内（0~k）的数，使用大小分别为n、k、n的数组a、b、c。根据 c 中小于 x 的个数，将元素放到 b 的指定位置。
基数排序
基本思想是根据数字每一位的大小进行排序。
桶排序
基本思想是将待排序元素放入桶中，每个桶分别排序，桶之间保持顺序。
LEC 5 分治法
分治法的思想，将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时的三个步骤：
分解步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决步骤递归的求解子问题，如果子问题的规模足够小，则停止递归直接求解。
合并步骤将子问题的解组合成原问题的解。
应用
二分搜索
归并排序
最大子数组问题
矩阵乘法的 Strassen 算法
Strassen 算法的运行时间的递归式为：
$T(n)=7T(n/2)+Θ(n^2)$
这里 a=7，b=2，$f(n)=Θ(n^2)$，即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1，则$T(n)=Θ(n^{lg7})$。
最近点对算法
最近点对算法的递归式为：
$T(n)=2T(n/2)+O(n)$
这里 a=2，b=2，$f(n)=O(n)$，即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2，则$T(n)=O(nlgn)$。
LEC 6 随机化算法
雇佣关系
快速排序
随机化算法的分类
Las Vegas 算法 ：总能给出正确的解或者无解。
Monte Carlo 算法 ：大多数给出正确解，错误率可以控制在一定程度上。
如检查两个长串是否相同，直接比较为 Las Vegas 算法，验证指纹则为 Monte Carlo 算法。
LEC 7 统计算法
LEC 8 动态规划
简介
动态规划（dynamic programming），这里的 programming 不是编程的意思，而是表格的意思，意味着将求出的子问题的解存到表格中，以便下次用到时直接查表取出。动态规划与分治法类似，都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。
原理
适合用动态规划求解的问题的两个要素：最优子结构和子问题重叠。
步骤
动态规划求解的一般步骤：
（1）刻画一个最优解的结构特征。
（2）递归地定义最优解的值。
（3）计算最优解的值，通常采用自底向上的方法。
（4）利用计算出的信息构造一个最优解。
应用
动态规划有着很规范的范式，一般按照步骤来。
最长公共子序列
刻画最长公共子序列的特征
我们很容易用“剪切-粘贴”技术证明：两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。
一个递归解
计算 LCS 的长度
我们使用两个表 c 和 b。
构造 LCS
沿着表 b 的箭头方向，从右下角开始，打印出公共元素即可。
作业排程
钢条切割
矩阵链乘法
矩阵链乘法就是寻找一个最优括号化方案，使得需要的标量乘法计算次数最少。
最优括号化方案的结构特征
最优括号化方案拥有最优子结构，我们可以使用“剪切-粘贴”方法很容易得证明，最优括号化方案包含其子链的最优括号化方案。
一个递归求解方案
计算最优代价
伪代码：
1 | MATRIX-CHAIN-ORDER(p) |
构造最优解
设计一个算法输出括号化方案。
LEC 9 贪心算法
简介
贪心算法和动态规划算法一样，通常用来求解最优化问题。
贪心算法的思想是每一步都选择局部最优解，很多时候这种方法能得到最优解，而且速度比动态规划快很多，也更简单。
原理
并没有确定的方法简单证明一个问题是否适用贪心算法。
但贪心选择性质和最优子结构是两个关键要素。
步骤
（1）将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
（2）证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。
（3）证明做出贪心选择后剩余的子结构满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
应用
活动选择问题
霍夫曼编码
最小生成树
单源最短路径的 Dijkstra 算法
LEC 10 图算法
图的表示和存储方式
邻接链表 邻接矩阵
邻接链表因为在表示稀疏图时非常紧凑而成为通常的选择。
在稠密图的情况下，我们可能倾向于使用邻接矩阵表示法。快速判断任意两个节点之间是否有边相连，可能也需要使用邻接矩阵表示法。
LEC 11 最小生成树
LEC 12 单源最短路径
单源最短路径
单源最短路径问题是从源结点到其它结点的最短路径问题。
一般解决方案是 Bellman-Ford 算法，其允许负值权重的边。当存在负值环路时，算法返回不存在问题的解，否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。
还有著名的 Dijkstra 算法，其要求所有边的权重都为非负。其利用了贪心算法的思想，每次都选择最短路径。
LEC 13 全成对最短路径
全点对最短路径
全点对最短路径问题是从任一结点到其余结点的最短路径的问题。
如果不存在负值权重的边，可以用 Dijkstra 算法对每个结点进行操作。
还有一种利用动态规划思想的 Floyd-Warshall 算法，其要求可以存在负值权重的边，但不可以存在负值回路。
排序算法
| 排序方法 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 插入排序 | $O(n^2)$ | $O(n^2)$ |
| 合并排序 | $O(nlgn)$ | $O(nlgn)$ |
| 快速排序 | $O(nlgn)$ | $O(n^2)$ |
| 随机快速排序 | $O(nlgn)$ | - |
| 计数排序 | $O(n+k)$ | - |
| 基数排序 | $O(d(n+k))$ | $O(d(n+k))$ |
| 桶排序 | $O(n)$ | - |
最短路径
单源最短路径
单源最短路径问题是从源结点到其它结点的最短路径问题。
一般解决方案是 Bellman-Ford 算法，其允许负值权重的边。当存在负值环路时，算法返回不存在问题的解，否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。
还有著名的 Dijkstra 算法，其要求所有边的权重都为非负。其利用了贪心算法的思想，每次都选择最短路径。
全点对最短路径
全点对最短路径问题是从任一结点到其余结点的最短路径的问题。
如果不存在负值权重的边，可以用 Dijkstra 算法对每个结点进行操作。
还有一种利用动态规划思想的 Floyd-Warshall 算法，其要求可以存在负值权重的边，但不可以存在负值回路。
算法的正确性证明
图算法入门
所有结点对的最短路径问题
贪心算法
简介
贪心算法和动态规划算法一样，通常用来求解最优化问题。
贪心算法的思想是每一步都选择局部最优解，很多时候这种方法能得到最优解，而且速度比动态规划快很多，也更简单。
原理
并没有确定的方法简单证明一个问题是否适用贪心算法。
但贪心选择性质和最优子结构是两个关键要素。
步骤
（1）将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
（2）证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。
（3）证明做出贪心选择后剩余的子结构满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
应用
活动选择问题
霍夫曼编码
最小生成树
单源最短路径的 Dijkstra 算法
动态规划
简介
动态规划（dynamic programming），这里的 programming 不是编程的意思，而是表格的意思，意味着将求出的子问题的解存到表格中，以便下次用到时直接查表取出。动态规划与分治法类似，都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。
原理
适合用动态规划求解的问题的两个要素：最优子结构和子问题重叠。
步骤
动态规划求解的一般步骤：
（1）刻画一个最优解的结构特征。
（2）递归地定义最优解的值。
（3）计算最优解的值，通常采用自底向上的方法。
（4）利用计算出的信息构造一个最优解。
应用
动态规划有着很规范的范式，一般按照步骤来。
最长公共子序列
刻画最长公共子序列的特征
我们很容易用“剪切-粘贴”技术证明：两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。
一个递归解
计算 LCS 的长度
我们使用两个表 c 和 b。
构造 LCS
沿着表 b 的箭头方向，从右下角开始，打印出公共元素即可。
作业排程
钢条切割
矩阵链乘法
矩阵链乘法就是寻找一个最优括号化方案，使得需要的标量乘法计算次数最少。
最优括号化方案的结构特征
最优括号化方案拥有最优子结构，我们可以使用“剪切-粘贴”方法很容易得证明，最优括号化方案包含其子链的最优括号化方案。
一个递归求解方案
计算最优代价
伪代码：
1 | MATRIX-CHAIN-ORDER(p) |
构造最优解
设计一个算法输出括号化方案。
分治法
分治法的思想，将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时的三个步骤：
分解步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决步骤递归的求解子问题，如果子问题的规模足够小，则停止递归直接求解。
合并步骤将子问题的解组合成原问题的解。
分析分治算法
应用
归并排序
最大子数组问题
矩阵乘法的 Strassen 算法
Strassen 算法的运行时间的递归式为：
$T(n)=7T(n/2)+Θ(n^2)$
这里 a=7，b=2，$f(n)=Θ(n^2)$，即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1，则$T(n)=Θ(n^{lg7})$。
最近点对算法
最近点对算法的递归式为：
$T(n)=2T(n/2)+O(n)$
这里 a=2，b=2，$f(n)=O(n)$，即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2，则$T(n)=O(nlgn)$。
线性时间排序
算法渐进分析
概率分析和随机化算法
算法导论
算法复习
数据结构研究组织大量数据的方法，算法分析则是对算法运行时间的评估。
算法是为求解一个问题需要遵循的、被清除地指定的简单指令的集合。
数据结构在计算机科学界至今没有一个标准的定义
普遍认可的算法的定义：算法是解决特定问题求解步骤的描述。
算法的特性：
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
引论
数学知识
级数：
证明方法
- 归纳法
- 反证法
递归简论
- 设计递归的基本法则：
- 基准情形
- 不断推进
- 设计效益：假设所有的递归调用都能运行。
- 合成效益法则：不要做重复性工作。
- 设计递归的基本法则：
算法分析
数学基础
$O(f(N))$ 上限
$Ω(f(N))$ 下限
$Θ(f(N))$ 相等
$o(f(N))$ 小于
表、栈和队列
表
- 数组
- 链表
栈
中缀表达式转换为后缀表达式：
中缀表达式可以通过栈转换成后缀表达式，P54
后缀表达式转换成表达式树同样借助栈：P71
扫描后缀表达式，若遇到operator，构造单节点树，入栈；
若遇到operand，从栈中弹出两棵树，以operand为根，合并弹出的两棵树，将得到的树入栈
时间复杂度=表达式的长度
队列
1
2
3
4
5struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};CreateQueue()IsFull()IsEmpty()Enqueue()Dequeue()
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
68
69// 队列的数组实现
// Created by aoyun on 2019/11/24.
//
typedef int ElementType;
typedef int Position;
struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;
static Queue CreateQueue(int MaxSize) {
Queue Q = (Queue) malloc(sizeof(struct QNode));
Q->Data = (ElementType *) malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = -1; // ZJU代码有错
Q->MaxSize = MaxSize;
return Q;
}
static bool IsFull(Queue Q) {
return ((Q->Rear + 1) % Q->MaxSize == Q->Front);
}
/**
*
* @param Q
* @param X
* @return 是否入队成功，队列已满会失败
*/
static bool AddQ(Queue Q, ElementType X) {
if (IsFull(Q)) {
printf("队列满");
return false;
} else {
Q->Rear = (Q->Rear + 1) % Q->MaxSize; // 队尾向后移
Q->Data[Q->Rear] = X;
return true;
}
}
static bool IsEmpty(Queue Q) {
return (Q->Front == Q->Rear);
}
ElementType DeleteQ(Queue Q) {
if (IsEmpty(Q)) {
printf("队列空");
return ERROR;
} else {
Q->Front = (Q->Front + 1) % Q->MaxSize;
return Q->Data[Q->Front];
}
}
int main() {
Queue Q = CreateQueue(4);
AddQ(Q, 1);
AddQ(Q, 2);
AddQ(Q, 3);
AddQ(Q, 4);
printf("\n%d", DeleteQ(Q));
}
树
二叉树
最多两个子节点
二叉查找树
每一个根节点，左子树的所有元素比根节点小，右子树相反。
AVL树
有条件的平衡树
伸展树
树的遍历
B-树
在2m阶B树中关键码个数n与B树高度h之间的关系为 $h≤log_m((n+1)/2)+1$
散列
- 散列函数
- 分离链接法
- 开放定址法
- 再散列
- 可扩散列
优先队列
二叉堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/*----------- 建造最大堆 -----------*/
/* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
void PercDown(MaxHeap H, int p) {
int Parent, Child;
ElementType X;
X = H->Data[p]; /* 取出根结点存放的值 */
for (Parent = p; Parent * 2 <= H->Size;) {
Child = Parent * 2;
if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
Child++; /* Child指向左右子结点的较大者 */
if (X >= H->Data[Child])
break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] = H->Data[Child];
Parent = Child;
}
H->Data[Parent] = X;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void MaxDown(MaxHeap H, int p) {
int Parent, Child; // Parent-父节点在数组中的指针 Child-子节点在数组中的指针
int X;
X = H->Data[p];
for (Parent = p; Parent * 2 < H->Size;) { // 从上往下，找p的正确位置
Child = Parent * 2; // Child在Parent*2处
if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1])) {
Child++; // 找到较大的Child
}
if (X > H->Data[Child]) { // p就是正确位置
break;
} else { // 子节点更大，把子节点数值赋值到父节点位置
H->Data[Parent] = H->Data[Child];
}
Parent = Child; // 父节点转到Child位置，重新开始新的一轮寻找父节点正确位置的过程
}
H->Data[Parent] = X;
}
应用
d-堆
左式堆
斜堆
二项队列
排序
冒泡排序
选择排序
插入排序
向扑克牌一样，把新元素插入到正确的位置
希尔排序
缩小增量的插入排序
堆排序
- 堆的构造
- 下沉排序
利用堆的性质进行排序
归并排序
分治。先分，分成小单位；再治，对小单位排序；最后合并。
==快速排序==
桶排序
知道元素的范围
基数排序
次位优先
表排序
大型结构的排序，移动不能
外部排序
不相交集
图论算法
- 定义
- 拓扑排序
- 最短路径
- Dijkstra算法 单源最短路径
- Floyd算法 多源最短
- 网络流
- 最小生成树
- Prim
- Kruskal
- 深度优先搜索
- NP-完全性
算法设计技巧
贪婪算法
分治算法
动态规划
核心思想：
将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
随机化算法
回溯算法
更多
广度优先搜索
复杂度总结
- BuildHeap
1 | // |
摊还分析
高级数据结构及其实现
软件工程
MATLAB入门
Windows 驱动程序入门
WDF Windows Driver Frameworks Windows 程序驱动程序框架
INF driver setup information 设备安装信息
编码
JSON
JSON (JavaScript Object Notation)
Android KTX
Material Design入门
WorkManager入门
文档补完-HTML
dp sp px
Android Animation
Activity之间跳转
Room入门
SQL入门
REST
文档补完-Android API reference
View绘制
要绘制东西，需要 4 个基本组件：存储像素点的 Bitmap、主持绘制的 Canvas、绘图的基本元素（Path，Rect，text，Bitmap等）、描述颜色和样式的 Paint。
Git
Vim
文档补完-Android Plugin DSL
Android自定义View
自定义 View 有两种方法：
继承 View 的子类，如TextView；
直接继承 View 类。需要自己绘制 UI 元素。
Android常用库
1 | // 2020-3-29 19:45:53 |
Dagger入门
Navigation入门
Navigation 组件由下面3个关键部分组成：
Navigation Graph XML resource 包含与navigation有关的所有信息，如destination path等。
NavHostFragment Layout XML 添加到layout的widget，显示了Navigation Graph的destination。
NavController Kotlin/Java 对象 追踪在 Navigation Graph 中的位置，协调那些destination。
Kotlin空安全
Kotlin协程
配置（Android）
1 | // kotlin coroutines |
示例：加载网络图片
1 | class MainActivity : AppCompatActivity() { |
withContext()可以切换到指定的线程，然后在闭包内的逻辑结束后，再切换到原来的线程继续执行。
Dispatchers
2020-03-21 22:09:50
CSS入门
HTML入门
Kotlin上路
译·RxJava
HTTP协议
Service入门
Service是一种可以在后台执行长时间运行操作而不提供界面的应用组件。
Gradle in Android
Android 构建时会编译源代码和应用资源，然后打包为APK文件。Android Studio 使用 Gradle 来自动执行和管理构建流程。Android Plugin for Gradle 与 Gradle 搭配使用，专门为 Android 应用的构建提供支持。
Data Binding入门
Shell脚本编程入门
新建脚本
1 | vim cnt.sh |
逐行显示指定文件的每一行内容并统计总行数
Gradle入门
Groovy入门
LeetCode
Kotlin入门
数字逻辑
Activity的生命周期
Linux内核编译
Python入门
2-Java注解
1-Java反射
编译别人ASProject的一些坑
报错：
Hello World
Welcome to Hexo!