版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第一章第一章 算法在计算中的应用算法在计算中的应用 第九章第九章 中位数和顺序统计学中位数和顺序统计学 9.1-19.1-1 【算法思想】: 1.将数组中的元素分组,每组两个元素,然后比较每组中的两个元素得到最小值,重新得 到包含原来一半元素的数组,继续重复上述过程,那么最后一个元素必然为最小值。如图 所示,数组为2, 1, 4, 3, 5 2.上述过程形成的是一个二叉树,其中叶子节点都为数组元素,非叶子节点刚好 4 个,这 是二叉树的性质。 3.然后我们来找第二小元素,第二小元素必然跟着 1,首先赋值为 5,然后再赋值为 3, 然后赋值为 2,即为所求。 【运行结果】: 1.我们先将 N 个
2、数配对,每两个数一对,每对之间进行互相比较得出小值。 2.对得出的 N/2个元素重复第一步,直至得出最小值。 到这儿我们得出了最小值,实际上比较的次数为 n-1次。不难发现上面的过程实际上可以 演示为一个二叉树。例如在5,8,11,18四个数找出最小值,二叉树演示如下(每个节点相当 于一次比较): 观察二叉树,可以得出这样一个结论,所有与最小值比较过的数中的最小值纪即为第二小 的的值。二叉树的高度为 lgn,因此与最小值比较的数的数目为 lgn,在 lgn 个数中找出最小 值要进行 lgn-1次比较。 9.1-2 9.3节的方法可以在最坏情况下的线性复杂度的算法来求顺序统计量.其核心思想在于获
3、得一 个更好的中枢值来更好地划分数组.然而题中给了我们一个黑盒子来以线性复杂度获取一 个真正好的中枢值,那么再好不过了。 在同时找到最大值和最小值时,每个元素都参与了与最大值和最小值的比较,比较了两次。 将数组成对处理。两两互相比较,将大的与最大值比较,小的与最小值比较。每两个元素 需要的比较次数是,两两比较一次,大者与最大值比较一次,小者与最小值比较一次,共 三次。 9.2-1 长度为 0 的数组,RANDOMIZED-SELECT 直接返回,当然不会递归调用。 9.2-2 9.2-3 写出 RANDOMIZED-SELECT 的一个迭代版本 【算法思想】: 递归:在函数中调用自身的程序过程
4、。深度优先。 递归是在函数内调用本身,迭代是循环求值 递推:用堆栈来代替递归要完成的过程。可实现广度优先或深度优先。 迭代:深度是可以预见的,所以不需要递归和递推来实现,直接把代码嵌套写下去就行。 for for for 就是典型的迭代。在这里,顺便实现在数组内寻找第 i 小的数值。 【运行结果】: 9.2-4 见书 9.3-1 9.3-29.3-2 9.3-39.3-3 9.3-49.3-4 9.3-59.3-5 9.3-69.3-6 9.3-79.3-7 【算法思想】: 1.找到数组 a 中第 n/2 小的数 median; 2.对 a 中非 median 数进行|ai - median|
5、,得到一个大小为 n - 1 的数组 distance; 3.寻找 distance 中第 k 小的数值; 4.对 distance 进行一次遍历,找到小于等于 k 的数,从而对应得到数组 a 中的 k 个数。 上述每一步的时间复杂度都为 O(n),因而最后总的时间复杂度为 O(n)。 【运行结果】: 9.3-89.3-8 【算法思想】: 该算法类似于二分查找算法 1.两个数组中小于 median 的个数为(n - 1)个,假设该 median 为数组 a 中的第 k 个,k 为 数组下标,那么在数组 a 中已经存在 k 个值小于 median,那么在数组 b 中必然有(n - 1) - k
6、= (n-k-1)个数小于 median,如果 bn - k - 2 = median = bn - k - 1,则搜索数组 a 中k + 1, n - 1中的元素,如果 median = bn - k - 2,则搜索数组 a 中0, k - 1中的元素. 2.依次类推,类似二分查找,不断重新设置 low,high,middle 3.如果在数组 a 中没找到,则在数组 b 中找 【运行结果】: 9.3-99.3-9 【算法思想】: 1.当 n 为奇数时,其实就是求 median; 2.当 n 为偶数时,就是第 n/2 小和第 n/2 + 1 小的数为边界的闭区间的任何数。 其实这个证明还是蛮简
7、单的,可以移动 x 轴来观察情况,位于 median 处(n 为奇数)或 median 范围内(n 为偶数)时,设其距离为 min,当移动 x 轴时,移出这个范围,则可以发 现所有点(包括 median 点)到 x 轴的距离必然大于 min。画一下图,就会一目了然。 在这里用到了寻找第 i 小的数。 【运行结果】: 9.2 /RadomizedSelect /by Adoo 2011/10/17 #ifndef RADOMIZEDSELECT #define RADOMIZEDSELECT #includeQuickSort.h template Iter RadomizedSelect(It
8、er IBeg,Iter IEnd,int index) if(std:distance(IBeg,IEnd)2) return IBeg; auto apart=RadomPartition(IBeg,IEnd); / Dont forget add 1; int i=std:distance(IBeg,apart)+1; if(index=i) return apart; else return indexi ? RadomizedSelect(IBeg,apart,index):RadomizedSelect(+apart,IEnd,index-i); #endif Randomized
9、-Select 线性期望时间线性期望时间 PARTITION(A, p, r) /partition 过程 p 为第一个数,r 为最后一个数 1 x Ar /以最后一个元素作为主元 2 i p - 1 3 for j p to r - 1 4 do if Aj x 5 then i i + 1 6 exchange Ai Aj 7 exchange Ai + 1 Ar 8 return i + 1 RANDOMIZED-PARTITION(A, p, r) /随机快排的 partition 过程 1 i RANDOM(p, r) /i 随机取 p 到 r 中个一个值 2 exchange Ar
10、 Ai /以随机的 i 作为主元 3 return PARTITION(A, p, r) /调用上述原来的 partition 过程 RANDOMIZED-SELECT(A, p, r, i) /以线性时间做选择,目的是返回数组 Ap.r中的第 i 小 的元素 1 if p = r /p=r,序列中只有一个元素 2 then return Ap 3 q RANDOMIZED-PARTITION(A, p, r) /随机选取的元素 q 作为主元 4 k q - p + 1 /k 表示子数组 Apq内的元素个数,处于划分低 区的元素个数加上一个主元元素 5 if i = k /检查要查找的 i 等
11、于子数组中 Ap.q中的元素个 数 k 6 then return Aq /则直接返回 Aq 7 else if i k 8 then return RANDOMIZED-SELECT(A, p, q - 1, i) /得到的 k 大于要查找的 i 的大小,则递归到低区间 Ap,q-1中去查找 9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k) /得到的 k 小于要查找的 i 的大小,则递归到高区间 Aq+1,r中去查找。 第十章第十章 数据结构数据结构 10.1-1 书 P121 10.1-2 用 top1 指向数组第一个元素,用 top2
12、 指向数组最后一个元素,然后 PUSH 的时 候,它们向中间进发,POP 的时候向相应的方向减一。 Solution:令两个栈的栈底为一个数组的两端,这样的话可以充分利用整个数组,直到两个 栈顶相遇。关键在于怎么样来判断两个栈顶是否相遇,两种思路。 思路一思路一:设置哨兵(Sentinel):在栈顶的下一个位置存储一个特殊值来作为警戒线,如同 在通知另一个栈,到这个地方就是我的领地了,别再过来,哨兵随着栈的大小而移动,需 要注意的是哨兵在移动到新的位置的过程中,需将原来的哨兵撤销。示图: 但是哨兵需占有两个空间,实际的空间利用为 n-2而不是 n. 思路二思路二:与思路一相反,思路二将所有的未
13、利用空间全部标记为“未利用空间”用无穷 表示。栈的任何一次 Pop 操作以后,都需将原来的栈顶标记为未使用空间。在 Push 操作之 前,先判断栈顶之后的元素是否为未使用空间。如下图示: 两种不同的思路,恰恰如同大国奉行的国土攻守政策,思路一主防凡是我过领土,派 兵进驻边境,阻止外国倾入。思路二主攻凡是无主领地,我便派兵占领。南海问题是 一种怎么样的政策? 10.1-3 书 P121 10.1-4 重写 ENQUEUE 和 DEQUEUE,使之能处理队列的下溢和上溢 用一个数组 Q1.n来实现一个至多含 n-1 个元素的队列。属性 headQ指向队列的头, tailQ指向新元素将会被插入的地方
14、。当 headQ = tailQ时,队列为空。初始时,有 headQ = tailQ=1 QUEUE-EMPTY(Q) /判断队列是否为空 if headQ = tailQ then return true else return false QUEUE-FULL(Q) /判断队列是否已满 if tailQ = lengthQ then next = 1 else next = tailQ+1 if next = head(Q) then return true else return false ENQUEUE(Q,x) /进队操作 if QUEUE-FULL(Q) then error “
15、overflow” else QtailQ = x if tailQ = lengthQ then tailQ = 1 else tailQ = tailQ+1 DEQUEUE(Q) /出队操作 if QUEUE-EMPTY(Q) then error “underflow” else if headQ = lengthQ then headQ = 1 return QlengthQ else headQ = headQ+1 return QheadQ-1 10.1-5 再看看程序!再看看程序! 10.1-6 【解法】: 1.有两个栈 s1 和 s2,先往 s1 内插入 a,b,c,这做的都是
16、 enqueue 操作。 2.现在要做 dequeue 操作,即要得到 a,这时可以将 s1 中的元素全部弹出并存入 s2 中,这时 s2 中元素的顺序(从底部到顶部)为 c,b,a,这时做 s2.pop()操作即可得到 a。 3.如果继续做 enqueue 操作,比如插入 d,f,则把 d,f 插入到 s1 中, 4.此时若要做 dequeue 操作,则直接弹出 s2 中的 b,它是目前为止,呆得时间最长 的元素 5.若继续做 dequeue 操作,则 s2 弹出 c, 6.若继续做 dequeue 操作,则 s2 为空,此时做步骤 2 的操作, 7.以此类推,就实现了用两个栈来实现一个队列
17、的目的。 插入操作的时间为 O(1),删除操作的时间=O(n),即小于线性时间,有时可能为 O(1). Implement a queue using two stacks. Denote the two stacks S1 and S2. The ENQUEUE operation is simply implemented as a push on S1. The dequeue operation is implemented as a pop on S2. If S2 is empty, successively pop S1 and push S2. The reverses the
18、 order of S1 onto S2. The worst-case running time is O(n) but the amortized complexity is O(1) since each element is only moved a constant number of times. Solutions:我将这个问题概括为桶饼模型:给俩个与饼同大的小桶,往桶中放饼,要求你在 拿饼的时候将先放进去的饼给拿出来。很显然,先放的饼在桶底,无法直接拿出,我们只 能借助于另一个桶把桶中的饼到往另一个桶中,原来桶底的饼就到了最上面,可以直 接拿到了。 完整的步骤为:将一个桶设为放
19、饼桶,另一个桶设为取饼桶。所有的放饼操作都在放饼桶 进行,并保证放饼之前,所有的饼已经都在放饼桶,若不在将取饼桶的饼倒入放饼桶,所 有的取饼操作都再取饼桶进行,取饼之前将放饼桶的饼倒入取饼桶。 以此模型类推,Dequeue 和 EnQueue 操作的复杂度都为 O(n).当连续进行 Dequeue 或连续 进行 EnQueue 操作时,它们的复杂度为1。 10.1-7 【解法】: 1.有两个队列 q1 和 q2,先往 q1 内插入 a,b,c,这做的都是栈的 push 操作。 2.现在要做 pop 操作,即要得到 c,这时可以将 q1 中的 a,b 两个元素全部 dequeue 并存入 q2
20、中,这时 q2 中元素为 a,b,对 q1 再做一次 dequeue 操作即可得到 c。 3.如果继续做 push 操作,比如插入 d,f,则把 d,f 插入到 q2 中, 4.此时若要做 pop 操作,则做步骤 2 5.以此类推,就实现了用两个队列来实现一个栈的目的。 注意在此过程中,新 push 进来的元素总是插入到非空队列中,空队列则用来保存 pop 操作之后的那些元素,那么此时空队列不为空了,原来的非空队列变为空了,总是这 样循环。 对于 push 和 pop 操作,其时间为 O(n)。 Solution:我一开始在纸上划了几个图,想快速找出方法,但总想不到可行办法,其实无形 中忽略了
21、问题的本质。栈的本质在于后进先出,抓住这一点问题就很快解决了。这个题的 实质就是要得到队列的最后一个元素,那么我们直接拿出前 n-1不就可以了。 具体步骤: 1.对于插入操作,将数据插入到有数据的那一个队列,若两队列都没有,随便插入一个队 列。 2.对于出栈操作,将有数据的一个队列中的数据一个个第拿出放入另一个队列,直到拿到 最后一个,该数就是要出栈的数。 算法复杂度,入栈复杂度为 O(1),出栈复杂度 O(n)。 10.2-1 书 P124 10.2-2 PUSH(S, x) next-topS topS-x POP(S) if topS=NIL then error Underflow e
22、lse x-topS topS-nextx return x 10.2-3 ENQUEUE(Q, x) nexttailQ-x nextx-NIL tailQ-x DEQUEUE(Q) if headQ=tailQ then error Underflow else x-nextheadQ headQ-x return x 10.2-4 Store the value you,re looking for in the sentinel. 10.2-5 循环链表插入,删除和查找的初步实现,但是感觉写的漏洞非常多,再研究研究 再看看程序!再看看程序! 10.2-6 public class Se
23、tOpt 2. 3. public List intersect(List ls, List ls2) 4. List list = new ArrayList(Arrays.asList(new Objectls.size(); 5. Collections.copy(list, ls); 6. list.retainAll(ls2); 7. return list; 8. 9. 10. public List union(List ls, List ls2) 11. List list = new ArrayList(Arrays.asList(new Objectls.size(); 1
24、2. Collections.copy(list, ls); 13. list.addAll(ls2); 14. return list; 15. 16. 17. public List diff(List ls, List ls2) 18. List list = new ArrayList(Arrays.asList(new Objectls.size(); 19. Collections.copy(list, ls); 20. list.removeAll(ls2); 21. return list; 22. 23. public static void main(String args
25、) 24. SetOpt opt = new SetOpt(); 25. List l1 = new ArrayList(); 26. l1.add(1); 27. l1.add(2); 28. l1.add(3); 29. l1.add(4); 30. List l2 = new ArrayList(); 31. l2.add(3); 32. l2.add(4); 33. l2.add(5); 34. l2.add(6); 35. List intersectList = ersect(l1, l2); 36. System.out.println(交集:); 37. for
26、(int i = 0; i intersectList.size(); i+) 38. System.out.print(intersectList.get(i) + ); 39. 40. System.out.println(); 41. List unionList = opt.union(l1, l2); 42. System.out.println(并集:); 43. for (int i = 0; i unionList.size(); i+) 44. System.out.print(unionList.get(i) + ); 45. 46. System.out.println(
27、); 47. List diffList = opt.diff(l1, l2); 48. System.out.println(差集:); 49. for (int i = 0; i diffList.size(); i+) 50. System.out.print(diffList.get(i) + ); 51. 52. System.out.println(); 53. 54. 55. 链结构的并查集 采用链式存储结构,在进行集合查找时的算法复杂度仅为 O(1) ;但合并集合时的算法复 杂度却达到了 O(n) 。如果我们希望两种基本操作的时间效率都比较高的话,链式存储方 式就“力不从心”了
28、。 树结构的并查集 采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同,每个顶 点纪录的不是它的子结点,而是将它的父结点记录下来。下面是树结构的并查集的两种运 算方式 直接在树中查询 边查询边“路径压缩” 对应与前面的链式存储结构,树状结构的优势非常明显:编程复杂度低;时间效率高。 直接在树中查询 集合的合并算法很简单,只要将两棵树的根结点相连即可,这步操作只要 O(1)时间复杂 度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。 因此直接查询所需要的时间复杂度平均为 O(logN) 。但在最坏情况下,树退化成为一条链, 使得每一次查询的算法复杂
29、度为 O(N) 。 边查询边“路径压缩 其实,我们还能将集合查找的算法复杂度进一步降低:采用“路径压缩”算法。它的想法 很简单:在集合的查找过程中顺便将树的深度降低。采用路径压缩后,每一次查询所用的 时间复杂度为增长极为缓慢的 ackerman 函数的反函数(x) 。对于可以想象到的 n,(n)都是在 5 之内的。 并查集(union-find sets)是一种简单的用途广泛的集合.它支持以下三中种操作: Union (Root1, Root2) /并操作;把子集合 Root2 并入集合 Root1 中.要求:Root1 和 Root2 互不相交,否则不执行操作. Find (x) /搜索操作
30、;搜索单元素 x 所在的集合,并返回该集合的名字. UFSets (s) /构造函数。将并查集中 s 个元素初始化为 s 个只有一个单元素的子集合. 对于并查集来说,每个集合用一棵树表示。 集合中每个元素的元素名分别存放在树的结点中,此外,树的每一个结点还有一个指向 其双亲结点的指针。 10.2-7 REVERSE(L) q-NIL while headL!=NIL do p-headL headL-nextp nextp-q q-p headL-q 【运行结果】: 10.2-8 每个结点,只存储前后指针值的异或值.这样的话,只要知道前后任何一个结点的地址,就可以 获得相反方向结点的地址,我用
31、了一个全局变量来跟踪上一个结点的地址.这样,在执行完 Find_L () 之后,便可以实现向前或者向后的遍历,这样一来,是可以实现双向链表应有的功能 的. 再看看程序!再看看程序! 10.3-1 见书 P126 10.3-2 10.3-3 10.3-4 用一个变量 m,表示链表中现有元素个数, 分析与解答:分析与解答: 假设链表中已有 y 个元素,并且已经紧凑排列。令 top = y +1,表示下一个将要分配 的指针位置 在分配空间时很简单: ALLOCATE-OBJECT 分配时,只需要 top+,同时在双链表 L 的头部增加一个元 素。 在释放空间时稍微复杂: FREE-OBJECT 释放
32、时,若 x 和 y 相同,则只需要从双链表 L 中删除元素 x,同时 top-;若 x m then error out of memory if headL NIL then prevheadL = y nexty headL prevy NIL headL y topfree topfree+1 FREE-OBJECT(x) y topfree-1 if nextx NIL then prevnextx prevx if prevx NIL then nextprevx nextx else headL nextx prevx prevy nextx nexty keyx keyy if prevy NIL nextprevy x if nexty NIL prevnex
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高中地理必修第二册《城乡内部空间结构》教学设计
- 九年级物理《电流 电流表》作业课教学设计
- 高中美术选修中国书画教学设计:方寸之间见精神-篆刻闲章与姓名印的文化解码与刀法实践
- 小学五年级音乐《卢沟谣》大单元整体教学设计:基于历史情境的家国情怀育人实践
- 初中科学酸碱盐综合应用教学设计
- 技术平权时代 2026年广东省AI大模型垂直应用内部创业孵化运营方案
- 双碳背景下:无人零售终端光伏自给与碳交易商业模式
- 山东省2027年春季高考语文全真冲刺模拟卷(三)
- 税务部门人员能力考核表
- 关于产品认证进展情况的确认函3篇范本
- (2026年)实施指南《DLT 1878-2018 燃煤电厂储煤场盘点导则》
- 双电源自动切换系统实验报告
- 初中语文阅读教学主问题设计:策略、实践与效能提升
- 《韧战》(2023年福建省中考满分作文15篇附审题指导)
- 艾灸治疗鼻炎
- 《相似植物如何区别》课件
- 驾驶员素质提升培训
- My family幼儿园家庭成员介绍手抄报
- 国家安全教育大学生读本-第一章完全准确领会总体国家安全观
- 《外科学》教案:第七章 麻醉
- 产后康复经络与腧穴
评论
0/150
提交评论