《算法导论》总结与分析

《算法导论》总结与分析,第1张

class="superseo">算法导论总结与分析
  • 分治
    • strassen算法
      • 介绍
      • 步骤
      • 正确性证明
      • 复杂度分析
  • 排序
    • 堆排序
      • 介绍
      • 步骤
        • 构建
        • 排序
        • 优先队列
      • 复杂度分析
    • 快速排序
      • 介绍
      • 步骤
      • 复杂度分析
        • 最坏情况
      • 最好情况

分治 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=B12B22S2=A11+A12S3=A21+A22S4=B21B11S5=A11+A22S6=B11+B22S7=A12A22S8=B21+B22S9=A11A21S10=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=A11S1P2=S2B22P3=S3B11P4=A22S4P5=S5S6P6=S7S8P7=S9S10

  • 根据计算得到的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+P4P2+P6C12=P1+P2C21=P3+P4C22=P5+P1P3P7

正确性证明
  • P 1 ⋯ P 7 P_1\cdots P_7 P1P7展开带入最后公式。
复杂度分析
  • 朴素算法求方阵乘积的时间复杂度是 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=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22

  • 得到时间复杂度公式如下

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=0lg n2k+1nO(h)=O(nk=0lg n2kh)O(nk=02kh)=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(n1)+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)

平衡情况下与最好情况类似

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1329917.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-12
下一篇 2022-06-12

发表评论

登录后才能评论

评论列表(0条)

保存