- 1、本文档共3页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Mark Allen Weiss 数据结构与算法分析 课后习题答案11
Chapter 11: Amortized Analysis
11.1 When the number of trees after the insertions is more than the number before.
11.2 Although each insertion takes roughly log NO , and each DeleteMinO takes 2log NO actual
time, our accounting system is charging these particular operations as 2 for the insertion
and 3log NO−2 for the DeleteMin.O The total time is still the same; this is an accounting
gimmick. If the number of insertions and DeleteMinsO are roughly equivalent, then it
really is just a gimmick and not very meaningful; the bound has more significance if, for
instance, there are NO insertions and OO (NO/ log NO) DeleteMinsO (in which case, the total
time is linear).
11.3 Insert the sequence NO , NO + 1, NO − 1, NO + 2, NO − 2, NO + 3, ..., 1, 2NO into an initially
empty skew heap. The right path has NO nodes, so any operation could take Ω(NO) time.
11.5 We implement DecreaseKey(X, H) as follows: If lowering the value of XO creates a heap
order violation, then cut XO from its parent, which creates a new skew heap HO 1 with the
new value of XO as a root, and also makes the old skew heap HO smaller. This operation
might also increase the potential of HO , but only by at most log NO . We now merge HO and
HO 1. The total amortized time of the MergeO is OO (log NO), so the total time of the
DecreaseKeyO operation is OO (log NO).
11.8 For the zigO−zigO case, the actual cost is 2, and the potential change is
R ( XO ) + R ( PO ) + R ( GO ) − R ( XO ) − R ( PO
您可能关注的文档
- 员工调查10-21-08Item15Employeesurvey.pdf
- E-Signature电子签名介绍.pdf
- 每 日 新 闻 读 卖2010-11-15.pdf
- 2013年1月15日黑色H管ROHS十项+四大卤素+四大重金属检测报告.pdf
- ISO 5904-1981 体育器械.自由体操用的着地垫和地板.阻滑移的测定.pdf
- 一阶导数形式不变性.pdf
- 大宇标准 EDS-T-7756-01.pdf
- 15BY45-83G规格书.pdf
- 3540S-1-201L;3540S-1-103L;3540S-1-102L;3540S-1-202L;3540S-1-502L;中文规格书,Datasheet资料.pdf
- GP-PROEX基础实践课程------第15章:配方.pdf
最近下载
- Roland罗兰乐器JUNO-Gi 带数字录音功能的便携合成器JUNO-Gi Workshop 04 Realtime Control in the JUNO-Gi支持文档.pdf
- 天正变频器TVFS9说明书.pptx VIP
- 人教版小学三年级上册语文期末.docx VIP
- SW7203数据手册_V13926596180高效率双向升降压.pdf VIP
- GB50070-2024-矿山电力设计规范.doc
- 学前教育_农村幼儿园户外游戏活动现状的调查研究.docx VIP
- 国开农村经济管理形考作业1-4试题及答案.pdf
- 嵌入式系统基础与实践基于ARMCortex-M3内核的STM32微控制器习题答案.pdf
- 学前教育_传统文化在幼儿园环境创设中应用现状调查.docx VIP
- 2024-2025学年人教版数学三年级上册期末测试卷.pdf VIP
文档评论(0)