algorithm-buaa-note

北航算法课程笔记

分而治之篇

归并排序

算法流程

分而治之一般步骤

分解原问题:原问题分解成多个子问题

解决子问题:递归地求解各个子问题

合并问题解:将结果合并为原问题解

归并排序伪代码

复杂度分析

递归式求解

递归树法

代入法

主定理法

递归式分析方法比较

分析方法	优点	缺点
递归树法	直观形象	难以展开
代入法	适用广泛	难猜通解
主定理法	形式简洁	适用有限

最大子数组问题 Ⅰ

子数组是数组 X 中连续的一段序列

形式化定义

一般步骤

伪代码及复杂度分析

本节讲述了三种不同的算法，用于解决最大子数组和问题:

算法名称	时间复杂度
蛮力枚举	$O(n^3)$
优化枚举	$O(n^2)$
分而治之	$O(n\log(n))$
动态规划	$O(n)$

逆序对计数问题

逆序对: 当 i<j 时 A[i]>A[j]的二元组(A[i],A[j])

伪代码

在本问题中，我们设计了四个算法：

算法名称	合并求解复杂度	时间复杂度
蛮力枚举	-	$O(n^2)$
分而治之+直接计算	$O(n^2)$	$O(n^2)$
分而治之+排序求解	$O(n\log(n))$	$O(n\log^2(n))$
分而治之+归并求解	$O(n)$	$O(n\log(n))$

多项式乘法问题

伪代码

本节讲述了三种不同的算法，用于解决多项式乘法问题:

算法名称	时间复杂度
蛮力算法	$O(n^2)$
朴素的分治	$O(n^2)$
改进的分治	$O(n^{\log(3)})$
快速傅里叶变换	$O(n\log(n))$

快速排序

伪代码及复杂度分析

排序算法比较

算法名称	时间复杂度
选择排序	$O(n^2)$
插入排序	$O(n^2)$
归并排序	$O(n\log(n))$
快速排序	最差:$O(n^2)$ 期望:$O(n\log(n))$

基于比较的排序，时间复杂度下界为$\Omega (n\log(n)) $

次序选择问题

如何求得数组中第 k 小的元素？

伪代码

算法名称	最好时间复杂度	最坏时间复杂度	期望时间复杂度
快速排序	$O(n\log(n))$	$O(n^2)$	$O(n\log(n))$
次序选择	$O(n)$	$O(n^2)$	$O(n)$

堆排序和线性时间排序

优化队列

优先队列是一种常用数据结构，支持下述两种操作：

• Insert： 将新元素插入队列中
• Extract-Min：返回队列中最小的元素并将其删除

(二叉)堆

堆可以视为一颗完全二叉树

• 除最后一层节点数可能不满外，其余层数的节点数目均达到最大个数
• 最后一层的节点都连续集中在最左边

算法名称	时间复杂度(平均)	时间复杂度(最坏)	额外空间	稳定性
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
归并排序	$O(n\log(n))$	$O(n\log(n))$	$O(\log(n))$	稳定
快速排序	$O(n\log(n))$	$O(n^2)$	$O(n\log(n))$	不稳定
堆排序	$O(n\log(n))$	$O(n\log(n))$	$O(1)$	不稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定

动态规划篇

0-1 背包问题

最大子数组问题