《算法导论》总结与分析

算法导论总结与分析

• 分治
• • 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​=B12​−B22​S2​=A11​+A12​S3​=A21​+A22​S4​=B21​−B11​S5​=A11​+A22​S6​=B11​+B22​S7​=A12​−A22​S8​=B21​+B22​S9​=A11​−A21​S10​=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​∙S1​P2​=S2​∙B22​P3​=S3​∙B11​P4​=A22​∙S4​P5​=S5​∙S6​P6​=S7​∙S8​P7​=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​+P6​C12​=P1​+P2​C21​=P3​+P4​C22​=P5​+P1​−P3​−P7​​

正确性证明

• 将 P 1 ⋯ P 7 P_1cdots 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​∙B21​C12​=A11​∙B12​+A12​∙B22​C21​=A21​∙B11​+A22​∙B21​C22​=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);

    //将堆尾元素置换到堆顶并缩小队列
    //=>等价于弹出堆顶并打乱堆秩序
	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(nsum^{lfloor lg n rfloor}_{k=0}frac{h}{2^{k}})Rightarrow O(nsum^{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)。

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

线性时间排序 介绍

• 利用格外存储空间排序。

步骤

计数排序

• 在数轴上记录每个数点的出现次数，累加后得到当前数点排序后的位置，插入数组。

桶排序

• 将均匀分布的数放到桶数组中，每个桶是一个列表，插入列表时按照大小排序，最后汇总。

复杂度分析

• 都是 O ( n ) O(n) O(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​​