算法设计与分析W5-动态规划

VIP免费

2025-01-13 3 0 1.43MB 130 页 5.9玖币

侵权投诉

Last Section

Divide and Conquer

•MINMAX:

2n –2 vs. 3n/2 –2

•二分搜索:

算法BINARYSEARCHREC在n 个元素组成的已

排序数组中搜索某个元素所执行的元素比较次数

不超过；

非递归；

•合并排序： nlogn

•寻找第 k 小元素：20cn

•划分算法与快速排序：n-1;n(n-1)/2

 

1log n

分治

•大整数乘法： n log 3 ≈n1.59

•矩阵乘法与STRASSEN 算法：nlog7 ≈n2.81

•最近点对：nlgn

减治

•插入排序: n2, n, n2/4

•快速排序+插入排序

•拓扑排序: 减一

•生成排列+ Johnson-Trotter

•生成子集+比特串方法

•假币问题

•俄式乘法

•约瑟夫斯问题

•欧几里德算法

•插值查找

•二叉查找树

变治_实例化简

•预排序

–检验数组中元素的惟一性： n(n-1)/2, nlogn+n

–模式计算： n(n-1)/2+n-1, nlogn+Θ(n)

•高斯消去法

–Partial pivoting

–LU 分解

–矩阵的逆

•AVL树: 1.39logn, 1.01logn

改变表现_ 2-3 树

•平衡一棵查找树的第二种思路是允许一个节

点不止包含一个键。

•2-3树是一种可以包含两种类型节点的树：

–2节点

–3节点。

2-3 树

•一个2节点只包含一个键K和两个子女（子节点）：

–左子节点作为一棵所有键都小于K 的子树的根

–右子节点作为一棵所有键都大于K的子树的根

（一个2节点和一棵经典二叉查找树的节点类型是相同的）

•一个3节点包含两个有序的键K1和K2（K1<K2）并

且有3个子节点：

–最左边的子节点作为键值小于K1的子树的根

–中间的子节点作为键值位于K1和K2之间的子树的根

–最右边的子节点作为键值大于K2的子树的根。

•2-3 树的最后一个要求是，树中的所有叶子必须位于

同一层：

–2-3 树总是高度平衡的

2-3 树的查找

•根是2节点：

–等同于二叉查找树

–比较于根键值：停止，左、右子树继续

•根是3节点：

–不超过两次比较

–比较于根键值：停止，左、中、右子树继续

2-3 树的插入

•如果插入位置的叶子是一个2节点

根据K 是小于还是大于节点中原来的键，我们把K作为第一个键或

者第二个键进行插入。

•如果叶子是一个3节点

把叶子分裂成两个节点：

-- 三个键（两个原来的键和一个新键）中最小的放到第一个叶子里

-- 最大的放到第二个叶子中

-- 中间的键提升到原来叶子的父节点中去（如果这个叶子恰好是树

的根，我们就创建一个新的根来接纳这个中间键）。

*中间键提升到父节点中去可能会导致父节点的溢出（如果它是一

个3节点），并且因此会导致沿着叶子的祖先链条发生多个节点的

分裂。

*例：为列表9，5，8，3，2，4，7 构造一 2-3树

2-3 树的效率

•一个具有最少节点的高度为h的2-3树是一颗全部由2节

点构成的满树。

•对于任何包含n个节点、高度为h的2-3树，有：

n ≥ 1+2+…+2h= 2h+1-1

则h≤log2(n+1)-1

•一个具有最多节点的高度为h的2-3树是一棵全部由3节

点构成的满树，每个节点都包含两个键和三个子女。

所以，对于任何n个节点的2-3树，有：

n ≤2·1 + 2·3 +…+ 2·3h= 2(1 + 3 + …+ 3h) = 3h+1 –1

则h≥log3(n+1)-1

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

LastSectionDivideandConquer•MINMAX:2n–2vs.3n/2–2•二分搜索:算法BINARYSEARCHREC在n个元素组成的已排序数组中搜索某个元素所执行的元素比较次数不超过；非递归；•合并排序：nlogn•寻找第k小元素：20cn•划分算法与快速排序：n-1;n(n-1)/21logn分治•大整数乘法：nlog3≈n1.59•矩阵乘法与STRASSEN算法：nlog7≈n2.81•最近点对：nlgn减治•插入排序:n2,n,n2/4•快速排序+插入排序•拓扑排序:减一•生成排列+Johnson-Trotter•生成子集+比特串方法•假币问题•俄式乘法•...

展开>> 收起<<

算法设计与分析W5-动态规划.pdf

共130页,预览26页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W5-动态规划

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: