分治
strassen算法
介绍
步骤
- 将方阵分块后，得到8个子方阵；
- 计算10个S矩阵；
S
1
=
B
12
−
B
22
S
2
=
A
11
+
A
12
S
3
=
A
21
+
A
22
S
4
=
B
21
−
B
11
S
5
=
A
11
+
A
22
S
6
=
B
11
+
B
22
S
7
=
A
12
−
A
22
S
8
=
B
21
+
B
22
S
9
=
A
11
−
A
21
S
10
=
B
11
+
B
12
\begin{aligned} &S_{1}=B_{12}-B_{22}\\ &S_{2}=A_{11}+A_{12}\\ &S_{3}=A_{21}+A_{22}\\ &S_{4}=B_{21}-B_{11}\\ &S_{5}=A_{11}+A_{22}\\ &S_{6}=B_{11}+B_{22}\\ &S_{7}=A_{12}-A_{22}\\ &S_{8}=B_{21}+B_{22}\\ &S_{9}=A_{11}-A_{21}\\ &S_{10}=B_{11}+B_{12} \end{aligned}
S1=B12−B22S2=A11+A12S3=A21+A22S4=B21−B11S5=A11+A22S6=B11+B22S7=A12−A22S8=B21+B22S9=A11−A21S10=B11+B12
- 通过8个子方阵和10个S矩阵做7次矩阵乘法，得到7个P方阵；
P
1
=
A
11
∙
S
1
P
2
=
S
2
∙
B
22
P
3
=
S
3
∙
B
11
P
4
=
A
22
∙
S
4
P
5
=
S
5
∙
S
6
P
6
=
S
7
∙
S
8
P
7
=
S
9
∙
S
10
\begin{aligned} &P_1=A_{11}\bullet S_{1}\\ &P_2=S_{2}\bullet B_{22}\\ &P_3=S_{3}\bullet B_{11}\\ &P_4=A_{22}\bullet S_{4}\\ &P_5=S_{5}\bullet S_{6}\\ &P_6=S_{7}\bullet S_{8}\\ &P_7=S_{9}\bullet S_{10} \end{aligned}
P1=A11∙S1P2=S2∙B22P3=S3∙B11P4=A22∙S4P5=S5∙S6P6=S7∙S8P7=S9∙S10
C
11
=
P
5
+
P
4
−
P
2
+
P
6
C
12
=
P
1
+
P
2
C
21
=
P
3
+
P
4
C
22
=
P
5
+
P
1
−
P
3
−
P
7
\begin{aligned} &C_{11}=P_5+P_4-P_2+P_6\\ &C_{12}=P_1+P_2\\ &C_{21}=P_3+P_4\\ &C_{22}=P_5+P_1-P_3-P_7 \end{aligned}
C11=P5+P4−P2+P6C12=P1+P2C21=P3+P4C22=P5+P1−P3−P7
正确性证明
- 将
P
1
⋯
P
7
P_1\cdots P_7
P1⋯P7展开带入最后公式。
复杂度分析
-
朴素算法求方阵乘积的时间复杂度是
O
(
n
3
)
O(n^3)
O(n3)。
-
方阵分块乘积时，若维度是2的倍数，可将每个方阵分为4个小方阵求乘积。
C
11
=
A
11
∙
B
11
+
A
12
∙
B
21
C
12
=
A
11
∙
B
12
+
A
12
∙
B
22
C
21
=
A
21
∙
B
11
+
A
22
∙
B
21
C
22
=
A
21
∙
B
12
+
A
22
∙
B
22
C_{11}=A_{11}\bullet B_{11}+A_{12}\bullet B_{21}\\ C_{12}=A_{11}\bullet B_{12}+A_{12}\bullet B_{22}\\ C_{21}=A_{21}\bullet B_{11}+A_{22}\bullet B_{21}\\ C_{22}=A_{21}\bullet B_{12}+A_{22}\bullet B_{22}
C11=A11∙B11+A12∙B21C12=A11∙B12+A12∙B22C21=A21∙B11+A22∙B21C22=A21∙B12+A22∙B22
T
(
n
)
=
{
O
(
1
)
n
=
1
8
T
(
n
/
2
)
+
O
(
n
2
)
n
>
1
T(n)= \left\{ \begin{aligned} &O(1) &n=1\\ &8T(n/2)+O(n^2) & n>1 \end{aligned} \right.
T(n)={O(1)8T(n/2)+O(n2)n=1n>1
T
(
n
)
=
{
O
(
1
)
n
=
1
7
T
(
n
/
2
)
+
O
(
n
2
)
n
>
1
T(n)= \left\{ \begin{aligned} &O(1) & n=1\\ &7T(n/2)+O(n^2) & n>1 \end{aligned} \right.
T(n)={O(1)7T(n/2)+O(n2)n=1n>1
- 推导出strassen算法求乘积时间复杂度为
O
l
g
7
O^{lg7}
Olg7。
排序
堆排序
介绍
步骤
构建
- DownAdjust(begin, end)将子树构建为堆。
//从begin_index到end_index向下调整堆
void Heap::DownAdjust(const int begin_index, const int end_index) {
//end_index超过堆大小则退出
assert(end_index <= tail_index_);
//father表示起始节点，child表示father对应的子节点
int father = begin_index, child = father * 2;
while (child <= end_index) {
//JudgeForOrder根据最大(小)堆特性来判断
//child选择更大(小)的子节点
if (child != end_index && JudgeForOrder(heap_[child + 1], heap_[child])) {
++child;
}
//child和father比较
if (JudgeForOrder(heap_[father], heap_[child]))
break;
//若child比father大(小)则交换节点值并迭代调整
std::swap(heap_[child], heap_[father]);
father = child;
child = child * 2;
}
}
- MakeHeap()调整每一个非叶子节点，完成建堆。
void Heap::MakeHeap() {
//从最后一个非叶子节点开始向前迭代
for (int i = heap_.size() / 2; i >= 1; --i) {
//调整以i为根节点的子堆
DownAdjust(i, tail_index_);
}
}
排序
- 根据堆的特性，通过每次将堆顶元素放到未排序堆尾并调整剩余堆，可将(大顶堆->降序)、(小顶堆->升序)。
void Heap::Sort() {
//保证堆是最大(小)堆
MakeHeap();
//从堆尾开始向前迭代
for (int i = tail_index_; i > 1; --i) {
//i之后的元素为已经排好序的元素
//每次将i节点元素与堆顶元素交换->打乱堆秩序
std::swap(heap_[i], heap_[1]);
//从堆顶向下调整
DownAdjust(1, i - 1);
}
}
优先队列
- 优先队列本质上是堆，在堆的基础上增加了出队列和入队列的操作。
void Heap::Pop() {
//队列为空不可出队列
assert(tail_index_ >= 1);
//将堆尾元素置换到堆顶并缩小队列
//=>等价于弹出堆顶并打乱堆秩序
heap_[1] = heap_[tail_index_--];
//从堆顶向下调整
DownAdjust(1, tail_index_);
}
void Heap::Push(const int val) {
//将元素插入到队尾
if (++tail_index_ < heap_.size()) {
heap_[tail_index_] = val;
} else {
heap_.push_back(val);
}
//从堆尾向上调整
UpAdjust(1, tail_index_);
}
- UpAdjust(begin, end)将向上调整堆。
//从end_index开始向上调整到begin_index
void Heap::UpAdjust(const int begin_index, const int end_index) {
//end_index<1时无效
assert(end_index >= 1);
//child表示起始节点，father表示child对应的父节点
int child = end_index, father = child / 2;
while (father >= begin_index) {
//child和father比较
if (JudgeForOrder(heap_[father], heap_[child]))
break;
//若child比father大(小)则交换节点值并迭代调整
std::swap(heap_[child], heap_[father]);
child = father;
father = child / 2;
}
}
复杂度分析
T
(
n
)
≤
T
(
2
n
/
3
)
+
O
(
1
)
T(n)\leq T(2n/3)+O(1)
T(n)≤T(2n/3)+O(1)
- 根据主定理推算出向下调整子堆的时间复杂度为
O
(
l
g
n
)
O(lg\ n)
O(lg n)。
-
建堆需要n/2次向下调整子堆（每次子堆高度不同），时间复杂度公式为
∑
k
=
0
⌊
l
g
n
⌋
⌈
n
2
k
+
1
⌉
O
(
h
)
=
O
(
n
∑
k
=
0
⌊
l
g
n
⌋
h
2
k
)
⇒
O
(
n
∑
k
=
0
∞
h
2
k
)
=
O
(
n
)
\sum^{\lfloor lg\ n \rfloor}_{k=0}\lceil \frac{n}{2^{k+1}} \rceil O(h)=O(n\sum^{\lfloor lg\ n \rfloor}_{k=0}\frac{h}{2^{k}})\Rightarrow O(n\sum^{\infin}_{k=0}\frac{h}{2^{k}})=O(n)
k=0∑⌊lg n⌋⌈2k+1n⌉O(h)=O(nk=0∑⌊lg n⌋2kh)⇒O(nk=0∑∞2kh)=O(n)
快速排序
介绍
步骤
- Partition(…)找到中间元素下标。
- 若为递增排序，下标左边元素<=中间元素<=下标右边元素；
- 若为递减排序，下标左边元素>=中间元素>=下标右边元素。
//对任何支持比较运算符的类型兼容
//从start_index到end_index查找
//is_random表示是否使用随机元素
template<typename T>
int Partition(std::vector<T>& origin,
const int start_index,
const int end_index,
const bool is_random) {
//找范围内随机下标元素置换到末元素
if (is_random) {
decltype(uniform)::param_type param{ start_index, end_index };
uniform.param(param);
std::swap(origin[uniform(gen)], origin[end_index]);
}
//末元素的值作为中间值
T mid_value = origin[end_index];
//index表示比中间值小的最后一个位置
int index = start_index - 1;
//从start_index到end_index前一个
//将比中间值小(大)的元素放到左边
for (int i = start_index; i < end_index; ++i) {
if (JudgeForOrder(mid_value, origin[i])) {
std::swap(origin[i], origin[++index]);
}
}
//将末元素换到划分数组位置
std::swap(origin[end_index], origin[++index]);
//返回划分数组位置
return index;
}
//对任何支持比较运算符的类型兼容
//从start_index到end_index排序
//is_random表示是否使用随机元素
template<typename T>
void Sort(std::vector<T>& origin,
const int start_index,
const int end_index,
const bool is_random) {
//临界值，表示不需要排序(无内容)
if (start_index >= end_index)
return;
//获取中间分割点
int privot = Partition(origin, start_index, end_index, is_random);
//递归排序左数组
Sort(origin, start_index, privot - 1, is_random);
//递归排序右数组
Sort(origin, privot + 1, end_index, is_random);
}
复杂度分析
- Partition在子数组上只需要一次遍历，故时间复杂度为
O
(
n
)
O(n)
O(n)。
最坏情况
- 划分时选定的坐标总是为范围内最大(小)值，导致小数组被划分为n-1和1，该种情况下时间复杂度公式为
T
(
n
)
=
T
(
n
−
1
)
+
O
(
n
)
T(n)=T(n-1)+O(n)
T(n)=T(n−1)+O(n)
- 得到时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
最好情况
- 划分时恰好为数组中间位置，数组被划分为n/2和n/2，时间复杂度公式为
T
(
n
)
=
2
T
(
n
/
2
)
+
O
(
n
)
T(n)=2T(n/2)+O(n)
T(n)=2T(n/2)+O(n)
- 得到时间复杂度为
O
(
n
l
g
n
)
O(nlg\ n)
O(nlg n)。
平衡情况下与最好情况类似
线性时间排序
介绍
步骤
计数排序
- 在数轴上记录每个数点的出现次数，累加后得到当前数点排序后的位置，插入数组。
桶排序
- 将均匀分布的数放到桶数组中，每个桶是一个列表，插入列表时按照大小排序，最后汇总。
复杂度分析
数据结构
二叉搜索树
介绍
- 若存在左子树或右子树，保证
V
l
e
f
t
≤
V
r
o
o
t
≤
V
r
i
g
h
t
V_{left}\leq V_{root}\leq V_{right}
Vleft≤Vroot≤Vright（或者
V
l
e
f
t
≥
V
r
o
o
t
≥
V
r
i
g
h
t
V_{left}\geq V_{root}\geq V_{right}
Vleft≥Vroot≥Vright）。
复杂度分析
- 所有操作都是
O
(
n
)
O(n)
O(n)。
- 因为查询操作时间复杂度为
O
(
n
)
O(n)
O(n)，其他操作是基于查询的。
- 查询时间复杂度推导使用归纳法
T
(
0
)
=
c
T
(
n
)
≤
T
(
k
)
+
T
(
n
−
k
−
1
)
+
d
=
(
(
c
+
d
)
k
+
c
)
+
(
(
c
+
d
)
(
n
−
k
−
1
)
+
c
)
+
d
=
(
c
+
d
)
n
+
c
\begin{aligned} T(0)&=c&\\ T(n)&\leq T(k)+T(n-k-1)+d&\\ &=((c+d)k+c)+((c+d)(n-k-1)+c)+d&\\ &=(c+d)n+c& \end{aligned}
T(0)T(n)=c≤T(k)+T(n−k−1)+d=((c+d)k+c)+((c+d)(n−k−1)+c)+d=(c+d)n+c
