全文预览已结束
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第二次作业 2 2 1 2 2 2 参考算法如下 1 Select sort A n 2 for i 1 to n 1 3 min A i 4 index i 5 for j i 1 to n 6 if A j min 7 index j 8 min A j 9 if indexi 10 A index A i 11 A i min loop invariant 从A 1 到A j 1 这j 1个数是排好序的 并且是A中最小的j 1个数 Best case Worst case 因为不管是最好情况 还是最坏情况 两层循环的复杂度都是一样的 许多同学在第8行中 没有将min的值及时更新 这一点需要注意 另外 许多同学都没有对loop invariant 进行说明 2 3 3 证明如下 采用数学归纳法 1 当k 1时 n 2 显然有T n nlgn 2 假设当k i时公式成立 即T n nlgn 3 n 2 n 2 n iii i 22lg2 1 3 则当k i 1时 即n 时 T n T 2 T i i 1 lg n lgn 综上可得 T n nlgn 2 3 4 或 在n 1时T n c c表示常量级 或都可以 不要写成1 有些同学将n从2开始 没有 将n为1的情况包含进去 2 3 6 不能 虽然用二分查找法可以将查找正确位置的时间复杂度降下来 但是移位操作的复杂度并没有 降下来 所以最坏情况下该算法的时间复杂度依然是 不能降为 2 3 7 算法思想 首先要对n个数进行排序 用快排复杂度为 然后在在排序后的数组中查 找是否存在两数之和为x 查找可以用下面的方法 假设排序后数组中元素为非降序列 Search A n x QuickSort A n i 1 j n while A i A j x and i j if A i A j 1 1 1 1 nifnnT nif nT 1 1 1 nifdnnT nifc nT 1 2 n lg nn lg nn 2 3 i i 1 else j j 1 if A i A j x return true else return false 用这个方法查找的复杂度是的 许多同学都是先固定一个元素然后去二分查找x和这个 元素的差 复杂度为 不如这样好 但由于排序的关系 算法总体的复杂度依然是 这一题不仅要求给出算法 并要求分析所给算法的时间复杂度为 许多同学只是写 了伪代码 没有对算法的时间复杂度进行分析 另外一点需注意的是应指出选
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 北师大版九年级数学上册课堂教学设计
- 中学英语听说教学技巧总结
- 山东省青岛市市南区2023-2024学年八上期末数学试题(解析版)
- 2025年现场总线智能仪表项目合作计划书
- 初中地理课堂教学设计模板
- 2025年吡唑啉酮项目合作计划书
- 酒店客户服务标准与流程
- 电影解说稿:海蒂和爷爷观后感
- 财务年度总结及次年工作计划模板
- 住家保姆服务合同示范文本
- lng应急预案安全培训课件
- 2025年健身运动与体能训练技术考试试题及答案解析
- 心理韧性:在困境中绽放的力量+课件-2025-2026学年高一上学期时代楷模主题班会
- 高分子材料概论橡胶课件
- 2025年学历类成考专升本-政治参考题库含答案解析(5套试卷)
- 围手术期感染预防措施
- 建设工程停工承包人费用计算标准T-YJXB-0001-2023知识解读
- 腰肌劳损知识课件
- 国内无人机物流发展现状
- 六年级上册数学第一单元测试卷(附答案)北京版
- 学堂在线 海上求生与救生 期末考试答案
评论
0/150
提交评论