算法设计与分析基础
2019-10-24 10:03:52 9 举报AI智能生成
算法设计与分析基础
作者其他创作
大纲/内容
绪论
什么是算法
算法问题求解基础
理解问题
需求分析（目标与功能）
确定问题类型
考虑可用算法
了解设备性能
是否支持并行计算
计算速度
内存容量
在精确解法和近似解法之间做出选择
算法的设计技术
蛮力法（穷举法）
减治法
分治法
变治法
动态规划
贪婪技术
回溯法
确定适当的数据结构
算法的描述
文字
伪代码
流程图
算法的正确定证明
数学归纳法
反证法
算法的分析
时间效率
空间效率
为算法写代码
重要的问题类型
排序
键
有序列表
特性
稳定性
额外存储空间(在位)
查找
查找键
字符串处理
字符串匹配
图问题
图的遍历算法
最短路线算法
有向图的拓扑排序
组合问题
几何问题
最近对问题
凸包问题
数值问题
基本数据结构
列表
栈
先进后出
队列
先进先出
堆->实现
优先队列
查找最大元素
删除最大元素
插入新的元素
线性数据结构
数组
实现字符串，位串
链表
单链表
双链表
图
图的表示法
邻接矩阵
链接表
加权（有向）图
路径和环
路径
连通性
无环性
树
自由树
森林
特性
|E|=|V|-1
有根树
空间状态树
回溯法
分支界限
有序树
二叉树
二叉查找树
多路查找树
集合与字典
集合
通用集合
线性列表结构
字典
查找
增加
删除
算法效率分析基础
分析框架
输入规模的度量
运行时间的度量单位
时间的标准度量单位
每一步操作的执行次数
时间效率
对于输入规模n，基本操作的运行次数T（n）=copC（n）
n大：关注执行次数的增长次数及其常数倍
n小：用指数级操作次数的算法解决
空间效率
算法消耗的额外存储单元的数量
增长次数
对数函数：log n
指数级
幂函数
阶乘函数
算法的最优、最差和平均效率
分析框架概要
渐近符号和基本效率类型
符号O
t（n）∈O（g（n））
存在大于0的常数c和非负整数n0，对于所有的n>=n0，t（n）<=cg（n）
符号Ω
t（n）∈Ω（g（n））
存在大于0的常数c和非负整数n0，对于所有的n>=n0，t（n）>=cg（n）
符号θ
t（n）∈θ（g（n））
存在大于0的常数c1，c2，和非负整数n0，对于所有的n>=n0，c2g（n）<=t（n）<=c1g（n）
用极限比较增长次数
求极限
洛必达法则
史特林公式
基本的效率类型
1--常数
logn--对数
n--线性
nlogn--线性对数
n2--平方
n3--立方
2的n--指数
n！--阶乘
非递归算法的数学分析
决定哪个（哪些）参数表示输入规模
找出算法的基本操作（位于最内层循环中）
找出基本操作的执行次数是否只依赖于输入规模。如果它还依赖于其他特性，啧最差效率，平均效率，以及最优效率需要分别研究
建立一个算法基本操作执行次数的求和表达式
利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数
递归算法的数学分析
决定哪个（哪些）参数表示输入规模的度量标准
找出算法的基本操作
检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。如果有这种克鞥，则必须对最差效率，平均效率，以及最优效率做单独研究
对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件
解这个递推式，或者至少确定它的解的增长次数（反向替换法）
例题：计算第n个斐波那契数
递归类型
分治法
减治法
减一法
求解递推关系式
前向替代法
反向替代法
二阶常系数线性递推式
子主题
蛮力法
选择排序和冒泡排序-排序
选择排序
算法平均、最差效率/键的比较次数：θ（n 的2次）
键的交换次数：θ（n），或n-1
冒泡排序
算法平均、最差效率/键的比较次数：θ（n的2次）
键的交换次数：θ（n的2次）
顺序查找和蛮力字符串匹配-查找
顺序查找
最差效率：θ（n）
平均效率：θ（n）
蛮力字符串匹配
最差效率：θ（nm）
平均效率：θ（n）
最近对和凸包问题的蛮力算法-几何
最近对
蛮力法效率：θ（n的2次）
θ（nlogn）
凸包问题
凸集合
凸包
极点
效率：θ（n的3次）
穷举查找（生成所有可行解，选出最优解）-组合问题
旅行商问题（TSP）
哈密顿回路问题
θ（n！）
背包问题
θ（2的n次）
分配问题
θ（n！）
深度优先查找和广度优先查找-图问题
深度优先查找-DFS
数据结构：栈
定点顺序的种类：两种顺序
边的类型（无向图）：树向边、回边
应用：连通性、无环性、关节点
邻接矩阵的效率：θ（|V|的平方）
邻接链表的效率：θ（|V|+|E|）
广度优先查找-BFS
数据结构：队列
定点顺序的种类：一种顺序
边的类型（无向图）：树向边、交叉边
应用：连通性、无环性、最少边路径
邻接矩阵的效率：θ（|V|的平方）
邻接链表的效率：θ（|V|+|E|）
减治法
减常量算法
插入排序
最差效率：θ（n的2次）
最好效率：θ（n）
平均效率：θ（n的2次），比最差快一倍，优于选择排序，冒泡排序
扩展
希尔排序Shell
拓扑排序
前提：无环有向图
定义：起始顶点排在结束定点之前
求解方法
方法一：DFS出栈遍历反过来
方法二：减一法（作图）
生成组合对象的算法
生成排列
插入法
优点：满足最小变化的要求
Johnson-Trotter法
移动元素，指向了较小元素则此元素可以移动，下一个序列与上一个序列仅仅交换了两个元素的位置
算法效率：θ（n！）
字典顺序法
生成子集
减治法生成幂集
设n为集合元素个数，则子集个数为2的n次方
位串法生成幂集
减常因子算法
用平方求幂
折半查找
前提：有序数组
算法效率：θ（logn）
目的：把查找键和给定有序数组的中间元素进行比较（小文件）
假币问题
减治法（减半）
减治法（减n/3）
俄式乘法 n x m
n是偶数：n x m = n/2 x 2m
n是奇数：n x m = (n-1)/2 x 2m + m
结束条件：1 x m = m
手写：n减半，m加倍，再将n为奇数的m的值加起来为n x m 的结果
约瑟夫斯问题
L（n，m）表示幸存者的初始位置
走一圈，规模减少 1/m
计算
n为偶数
L（n，m）=2L（n/2，m）-1
n为奇数
L（n，m）=2L（（n-1）/2，m）+1
减可变规模算法
欧几里得算法
计算中值和选择问题
选择问题基于划分的算法
划分一：Lomuto算法-快速选择
计算
s=k-1，中轴本身显然是第K小的元素
s>k-1，整个列表的第k小元素就是被划分在数组左边部分的第k小的元素
s<k-1，则中轴是数组右边部分的第（k-s）小元素
效率
最好效率：θ（n）
最差效率：θ（n的2次）
平均效率：θ（n）
划分二：Hoare算法
应用
第K个顺序统计量
给定列表的k个最小元素
给定列表的n-k个最大元素
插值查找
前提：有序数组
目的：找到用来和查找键进行比较的数组元素（大文件）
效率分析
平均效率：插值查找的键值比较次数小于log2log2 n+1次
最差效率：θ（n）
分治法
通用分治递推式：T（n）=aT（n/b）+f（n）
利用主定理可以无需精确求解递推式而得到效率类型/增长次数 P132
合并排序
划分：根据元素的位置
时间效率
最差效率：θ（nlogn）
平均效率：θ（nlogn）
空间效率
需要线性的额外空间
优点:稳定性好
变化形式
自底向上合并数组
多路合并排序
快速排序
划分：根据元素的值，划分后元素已经位于它在有序数组中的最终位置
划分算法：Hoare，交换条件i>=j
时间效率
最优效率：θ（nlogn）
最差效率：θ（n的2次）
平均效率：θ（1.39nlog2 n）
缺点
不稳定
需要一个堆栈来存储没被排序的子数组的参数，最小可以为O（logn），但差于堆排序的O（1）空间效率
二叉树遍历及相关特性
前序遍历
中序遍历
后序遍历
大整数乘法和Strassen矩阵乘法
大整数乘法
具有渐进增长效率：θ（n的log2 3次方/n的1.585次方）
Strassen矩阵乘法
效率：θ（n的log2 7 次方/n的2.807次方）
用分治法解最近对问题和凸包问题
变治法
实例化简
预排序
检验数组中元素的唯一性
模式计算
查找问题
几何算法
贪婪技术
高斯消去法
平衡查找树
改变表现
堆与堆排序
堆的概念
条件
父母优势
完全二叉树
特点
在任何从根到某个叶子的路径上，键值的序列是递减的
在同一节点的左右子树之间没有任何关系
特性
构造堆
自底向上
从最后一个父亲节点开始，进行交换，然后自顶向下调整---堆化
最差情况，键值的比较次数：C(n)=2（n-log2 （n+1））
自顶向下
把新的键值连续插入预先构造好的堆，现在最后一个叶子节点，然后检测父母优势，知道根节点
插入的时间效率：（不高于树的高度）O(logn)
从堆中删除最大的键
步骤
堆的规模-1
按照自底向上堆构造算法的做法，把K沿着树向下筛选，来对这个较小的树进行“堆化”
根的键和堆的最后一个键K做交换
删除的时间效率：O（logn）
堆排序
步骤
构造堆
删除最大键
时间效率
平均：O（nlogn）
最差：O（nlogn）
空间效率：在位，无需额外的存储空间
霍纳法则和二进制幂
霍纳法则---多项式
系数（如果存在等于0的系数，也要包含进来）
x=x0，第一个单元用来存储an，其他单元用来存储中间结果，用前一个单元的值（第二行的最后一个单元格）乘以x的值再加上当前（第一行的下一个）系数，就是表格下一个单元格的值
副产品-综合除法
计算p（x）在某些点x0上的值所产生的中间数，可以作为p（x）除以x-x0的商的系数（注意x整体降了一次），算法的最后结果，除了等于p（x0）还等于这个除法的余数
二进制幂---a的n次幂
从左至右二进制幂--左起
n的二进制位
乘法累乘器（第一个值为a）
从第二个二进制位开始
1：前一个值的平方再乘以a
0：前一个值的平方
扩展
计算M（n）：（b-1）<=M（n）<=2（b-1），其中b是代表指数n的位串的长度，b=（log2 n向下取整）+1
计算乘法次数：写出n的二进制位的位串，除了一个1，其他位置如果是1，则+2，如果是0，则+1，最后的和为最少的乘法次数
算法效率：θ（logn）------蛮力法需要n-1次乘法
从右至左二进制幂--右起
n的二进制位
项a的2的i次方（i是右到左0，1，……n）
累乘器
1：前一个的值（右边）乘以当前的项
0：不作计算
算法效率：θ（logn）------蛮力法需要n-1次乘法
问题化简
时空权衡
动态规划
三个基本例子
基本思路
找出最优解的性质，并且刻画其结构特征
递归地定义最优值
以自底向上的方式计算出最优值
根据计算最优值时得到的信息，构造一个最优解
比较分治法
同：将问题分为若干个子问题
别：分治法中各个子问题相互独立，动态规划中各个子问题允许相互交叠
币值最大化问题
找零问题
硬币收集问题
背包问题和记忆功能
最优二叉查找树
前提
集合中元素的查找概率已知
它在查找中的平均键值比较次数是最低的
步骤
主表
左标：1到n+1
上标：0到n
对角线为0
对角线上一行补充查找概率
求和
最左边开始，与该空格下一个之和找到最小
作直角三角形，计算概率和
右上角则为平均键值比较次数
根表（最优子树根的下标）
在概率相同的位置设置1-n
这个最小和一项对应的上标+1为相应位置的根表的值
作出最优查找二叉树
根据根表，右上角开始
效率
时间效率：θ（n的3次）
空间效率：θ（n的2次）
Warshall算法和Flody算法
Warshall算法---计算有向图传递闭包
有向图
第i个顶点到第j个顶点是否可达
长度为1
邻接矩阵A
任意长度
传递闭包T
可达：1
不可达：0
求解传递闭包
深度优先查找
广度优先查找
Warshall算法
步骤
先写有向图的邻接矩阵R（0）
画框，并且在有1的行（竖直的框）和有1的列（水平的框）划线
在框外线的交点即新增加的1
算法效率
θ（n的三次方）
Flody算法---计算完全最短路径---通用
加权连通图（有向或者无向）
完全最短路径问题（每个顶点到其他所有顶点之间的距离（最短路径的长度））
权重矩阵W
对角线为0
权重
不可达：∞
距离矩阵D
求解完全最短路径
Flody算法
步骤
先写权重矩阵D（0）
画框，并且在有1的行（竖直的框）和有1的列（水平的框）划线
在框外线的交点的值为本来的值与（框内行列值之和）的最小值
对角线还是为0
算法效率
θ（n的三次方）
贪婪技术
贪婪算法---解决最优问题
每一步满足的条件
可行性
局部最优
得到全局最优
不可取消
证明最优
数学归纳法
在接近问题目标的时候，贪婪算法那每一步的选择至少不比其他算法差
基于算法的输出
最小生成树算法
最小生成树定义（求一个给定加权连通图的最小生成树（权重最小的生成树（包含所有顶点的连通无环子图））问题）
Prim算法
顶点标记：树中最近点的名称以及相应边的长度（权重）
源
a（-，-）
可见集合
与树中的节点有相邻的
不可见集合
与树中的任何顶点都不相邻，加上-点与∞
效率
图-权重矩阵
优先队列-无序数组
θ（|V|的2次）
图-邻接链表
优先队列-最小堆
θ（|E|log |V|）
Kruskal算法
不相交子集
并查算法
Dijkstra算法--解加权图最短路径（单起点）
区别Prim算法
Prim：直接比较给定的权重
Dijkstra：把边的权重相加
顶点标记：树中最近点的名称以及权重与（最近点里面的值）的和
源
a（-，0）
可见集合
不可见集合
与树中的任何顶点都不相邻，加上-点与∞
n个节点，则有n-1次迭代
效率
图-权重矩阵
优先队列-无序数组
θ（|V|的2次）
图-邻接链表
优先队列-最小堆
θ（|E|log |V|）
哈夫曼树及编码
0 条评论
下一页
