首页 > 其他 > 详细

第二章上机实践报告

时间:2019-09-23 00:46:30      阅读:48      评论:0      收藏:0      [点我收藏+]

标签:tlist   操作   port   出现   基本操作   ear   

对于二分法的心得

1)设置输入一组数组a

2)asearch函数;search()函数中先找到数组a[]的中间下标,判断l和 r的值,如果l>r,则目标值不存在,输出-1;其余情况分为三类,数组中间值正好等于目标值,则输出下标和次数;数组中间值大于目标值,则进行在下标为(l, mid - 1)的数组递归;数组中间值小于于目标值,则进行在下标为(mid + 1, r)的数组递归。直到找到中间值与目标值相等的时候结束。

算法时间及空间复杂度分析:

二分搜索算法函数的时间及空间复杂度。在每一次迭代递归中,数组被分成一半,所以函数执行了O(log2n) 次,函数中基本操作所执行的次数为n/2+log2n+n/2,每一次执行常数级别O (1)次,所以时间复杂度在最坏情况下为O(log2n),故该算法时间复杂度为log2n。

该二分算法在循环迭代的时候只用了a, x, l,rmid,需要辅助空间为常数级别的,空间复杂读为O(1)。

另外一些心得体会

  这一次上机实验写得比较慢,第一道题第一种情况目标值不在数组范围内,没有用r<l 来判断,而是直接判断目标值在不在数组范围内,但是在测试点的时候出现部分错误,将这条语句位置改了多次,最后改用r<l

第二章上机实践报告

标签:tlist   操作   port   出现   基本操作   ear   

原文:https://www.cnblogs.com/redish/p/11570000.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号