算法第2章实践报告
2021/10/13 11:14:40
本文主要是介绍算法第2章实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 实践题目名称
二分法求函数的零点
- 问题描述
有函数:f(x)=x^5-15x^4+85x^3−225x^2+274x−121,已知f(1.5)>0,f(2.4)<0 且方程f(x)=0 在区间[1.5,2.4] 有且只有一个根,请用二分法求出该根。 提示:判断函数是否为0,使用表达式 fabs(f(x)) < 1e-7
- 算法描述
本题我们采用二分法递归求解。
由题意可得:f(x)在区间[1.5,2.4]上单调递减。首先,我们取start=
1.5,end=2.4,mid=(start+end)/2,判断f(mid)的取值情况,临界情况是:fabs(f(mid))<1e-7,直接找到根,返回mid;若f(mid)>0,则下一个求根区间变为[mid,end],若f(mid)<0,则下一个求根区间变为[start,mid]。不断重复以上操作,不断进行二分操作,直到递归结束,最后用setprecision(6)<<std::fixed保留小数点后6位输出mid。
- 算法时间及空间复杂度分析
(1)时间复杂度
本题我们用二分法将一个大规模问题n分解为两个小的子规模,子规模变为n/2,由于只需要处理其中一个子规模问题,所以该算法时间复杂度为T(n/2)=O(log n)由于最后不需要进行合并子问题,所以我们只需要考虑一开始的函数输入,时间复杂度为O(1)。
合并起来时间复杂度为O(log n)+O(1)=O(log n)
(2)空间复杂度
在整个二分搜索的过程中,只需要额外存储三个变量:start ,end 和 mid,所以空间复杂度是O(1)
- 心得体会
(1) 本次实践收获
进一步加深了对二分法求解问题的理解,以后面对大规模的问题是可以根据实际情况使用该方法解决,降低时间复杂度。
(2) 疑惑
在递归过程中,不写return会超时,但是好像可以运行,有点不理解为什么会这样,感觉是一定要写return的。
- 分治法的个人体会和思考
分治法适用于将大规模的子问题分解成若干个小规模子问题,并且小规模子问题更容易求解、若干个小规模子问题之间互相独立、和大规模问题的性质是一样的,分治法分为三个步骤:
分解:将原问题分解成一系列子问题。
解决:递归地解各个子问题。
合并:将子问题的结果合并成原问题的解。
这篇关于算法第2章实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南