三分算法 简述 操作过程 具体代码 时间复杂度分析
三分算法是基于分治思想的一种算法，他的适用范围为单峰函数，主要实现是在求出区间中点mid的同时在右半区间再求出一个中点midmid，然后根据大小进行下一步操作。
操作过程
假设我们要在l到r中查找最值，先取整个区间的中点。
double mid=(l+r)/2;
然后我们再取右半部分的中点midmid
double midmid=(mid+r)/2;
然后比较mid和midmid哪个更靠近最值，若mid更靠近最值，则舍弃右区间，若midmid更靠近最值则舍弃左区间。
if(fun(mid)>fun(midmid)) r=midmid; else l=mid;
具体代码
double ssearch(double l,double r){//在区间l到r中查找最大值,返回位置 double mid,midmid; while(l+1e-8<=r){ mid=(l+r)/2; midmid=(mid+r)/2; if(fun(mid)>fun(midmid)) r=midmid; else l=mid; } return l; }
时间复杂度分析
三分和二分类似，同样可以构建一颗递归树，二分把问题分为了两份三分则把问题分成了三份，每一份的处理是O(1),所以我们可以列出递推公式T(n) = T(n/3) + O(1)，由主定理可得T(n) = O(log n)，同样和二分都是log级别的，但三分的底数是3所以稍劣。