基础算法 - 二分与三分 - 蒟蒻复习基础
2018-07-18 01:15:42来源:博客园 阅读 ()
二分是一种常用而且非常精妙的算法,常常是我们解决问题的突破口。二分的基本用途是在单调序列或单调函数中做查找操作。因此,当问题的答案具有单调性时,就可以通过二分把求解转化为判定(根据复杂度理论,判定的难度小于求解)。进一步的,我们还可以通过三分(适用于求解凸性函数)解决单峰函数的极值以及相关问题。
- 二分
思想:分而治之。将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,(如果子问题的规模仍然不够小,,再划分为k个子问题),然后递归的求解这些子问题,最后用适当的方法将各个子问题的解合并成原问题的解。
方法:a)二分查找:在一个单调有序的集合或函数中查找一个解,每次分为左右两部分,判断解在哪个区间(并调节上下界),并直到找到目标元素。
int binary_search(int x) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (a[mid] == x) { return mid; } if (a[mid] < x) { l = mid + 1; } else { r = mid; } } return - 1; }
b)二分答案:(最大值最小或最小值最大这类问题)这类双最值问题常常选用二分法求解(二分之后,先假装自己确定答案),配合贪心,DP等算法,检验这个答案是否合理,将最优化问题转化为判定性问题。
c)代替三分:(对于单峰函数)二分导函数求函数极值。
例题:Bzoj1734 Poj2018 ... ...
题目描述
输入
5
7
1
17
13
10
输出
如果Dilhao给出其他任何三本书,其中的两本书难度差的最小值都小于7,所以ldxxx出题的最大复杂程度为7。
数据说明
对于 30%的数据: 2<=n<=20;
对于 60%的数据: 2<=n<=1000;
对于 100%的数据: 2<=n<=100000, 2<=m<=n, 0<=ai<=1000000000。
- 三分
适用于凸性函数的极值问题(二次函数就是一个典型的单峰函数)。与二分法强调函数的单调性不同,三分法强调函数的单峰性。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- 如何0基础学习C/C++? 2020-06-06
- 复习C++语法--基础篇 2020-05-27
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash