第二次作业.pdf_第1页
第二次作业.pdf_第2页
第二次作业.pdf_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第二次作业 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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论