二分查找及幂分查找的算法上机报告_第1页
二分查找及幂分查找的算法上机报告_第2页
二分查找及幂分查找的算法上机报告_第3页
二分查找及幂分查找的算法上机报告_第4页
二分查找及幂分查找的算法上机报告_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

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

文档简介

1、二分查找及幂分查找的算法上机报告一、二分查找的实现及时间复杂度分析1、测试数据：小例子测试时以手工输入进行测试正确性；/以0结束输入性能测试时以伪随机数生成的文件输入进行数据记录，并将所得结果录入txt文件中；2、元组返回的C+实现：以结构体代替元组，并通过new/delete返回结构体指针；简单封装max/min函数实现比较两数的大小，使程序清晰易读；3、二分查找的具体实现只剩一个元素：剩下两个元素：二分查找的递归实现：几个小例子：3、时间复杂度的计算和拟合n较小时为2的幂、偶数、奇数；n较大时为2的幂、偶数、奇数:数据项128120119655366000060013比较次数1901821

2、81983029276692779绘图分析及数据回归：分析结果：由上图，T(n)=1.5279n+55.5279。根据理论分析，当n为2的幂时每次递归终点是两个元素，因此T为3/2n-2；而当n非2的幂时，由于产生递归终点为1或2，增加比较次数。根据测试，一次的系数为1.5279接近3/2，而常数项55.5279则比-2大得多。由此，非2的幂进行二分查找增加查找次数，但提升数量级并不明显。二、幂分查找的实现及时间复杂度分析1、幂分的实现：将n转换成二进制数进行幂分查找；设置一个长为32的结构体数组存储可能返回的幂分结果；/一般int类型为4个字节，即最多由32位二进制1构成；遍历幂分的结果得出最终n的结果：2、几个小例子：3、时间复杂度的计算和分析：n较小时为2的幂、偶数、奇数；n较大时为2的幂、偶数、奇数：数据项128120119655366000060013比较次数192180179983049000090020绘图分析及数据回归：分析结果：由上图，T(n)=1.5000n+0.1716。相比较二分查找，一次项系数小了0.0279，常数项接近0，远小于55.5279；与理论上3/2n-2相比也极为接近。考虑到幂分汇总结果时遍历可能增加常数级别的比较次数，这个结果已

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论