- 分治
- 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
- 根据计算得到的P方阵组合求方阵乘积。
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
-
推导出方阵分块求乘积时间复杂度为 O 3 O^3 O3。
-
strassen算法的时间复杂度在方阵分块的基础上将子方阵的乘法次数缩减为7。
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);
//将堆尾元素置换到堆顶并缩小队列
//=>等价于d出堆顶并打乱堆秩序
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)
-
推导出建堆的时间复杂度为 O ( n ) O(n) O(n)。
-
堆排序的时间复杂度为 O ( n l g n ) O(nlg\ n) O(nlg n)。
- 利用分治的方法将大数组排序分为小数组排序。
- Partition(…)找到中间元素下标。
- 若为递增排序,下标左边元素<=中间元素<=下标右边元素;
- 若为递减排序,下标左边元素>=中间元素>=下标右边元素。
//对任何支持比较运算符的类型兼容
//从start_index到end_index查找
//is_random表示是否使用随机元素
template
int Partition(std::vector& 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;
}
- Sort(…)递归地调整小数组。
//对任何支持比较运算符的类型兼容
//从start_index到end_index排序
//is_random表示是否使用随机元素
template
void Sort(std::vector& 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)。
平衡情况下与最好情况类似
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)