首页 / 算法 / 算法录 之 二分和三分
算法录 之 二分和三分
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法录 之 二分和三分,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1094字,纯文字阅读大概需要2分钟。
内容图文
虽然你十分聪明伶俐,但是还是要说一下 二分 和 三分。
二分:
首先说一下二分不是二分,是二分。就是一分为二的二分。
先来一个例子:
现在有一个递增的序列 a(1), a(2)...a(n),然后让你查找 x 在不在这个序列里面?
显然最简单的做法就是一个for循环,从1到n,看看有没和x相等的。。。
这样确实不错,但是太慢了。。。需要n次才能找到。有没更好的做法呢?
有(要是没有的话我说这个干什么),那就是二分查找了。
首先判断 a(n/2) 和 x 谁大谁小,如果 x 大的话,那么显然x可能在 a(n/2+1) 到 a(n) 这个范围里面,而一定不会在 a(1) 到 a(n/2) 这个范围里面,因为递增嘛。。。然后再按同样的方法递归查找后半个区间就行了。
如果x小的话同理找前半个区间。
这样每次把区间变成原来的一半,那么就是 logN 级别的时间复杂度,对于长度 n=100000 的序列,只需要不到20次就能判断x了。。。
具体代码如下:
// 查找A数组是否存在x。 bool find(int A[],int N,int x) { int L=0,R=N-1,M; // left right middlewhile(R>L) { M=(L+R)/2; if(A[M]==x) return1; elseif(A[M]>x) R=M-1; else L=M+1; } if(A[L]==x) return1; return0; }
通俗的说,其实二分是针对一个单调函数,在这个函数的一个区间中查找,每次取区间的中点去判断,然后根据大小把区间变成原来的一半。。。然后一直这样下去就好。
二分的应用可以说是很广很广,具体的之后也会有练习题。
三分:
如果说二分针对的是单调函数,那么三分针对的是双调函数。也就是下面这样的函数。
三分是求这样先增后减或者是先减后增的函数的极值的。
具体步骤就是:对于区间 (L,R),先求出 1/3 处的 M1 和 2/3 处的 M2,然后比较 M1 和 M2 处的大小,如果 M1 处的值大于 M2 处的值,那么极值一定在(M1,R)这个区间范围内,否则一定在 (L,M2)这个范围内。
因为如果 M1处大于M2处的话,M1不可能在极值点的右边。。。所以。。。就是这样了。。。每次变成原来区间的2/3大小。。。
二分三分的用处很广很广,比如对一个符合的序列,或者是在计算几何中用来求一些不好算的值等等。。。
原文:http://www.cnblogs.com/whywhy/p/4886641.html
内容总结
以上是互联网集市为您收集整理的算法录 之 二分和三分全部内容,希望文章能够帮你解决算法录 之 二分和三分所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。