关于三分

回复帖子

@dxbdly 2019-05-15 14:23 回复

请问大佬们,在三分算法中,两个三分点为什么会在最优点两侧

@qwaszx 2019-05-15 14:26 回复

因为初值选得好

只要初值在顶点两端,那么每一次三分的过程都保证了这个性质成立

@dxbdly 2019-05-15 15:02 回复

@qwaszx 啥叫好的初值呢,如果最优点在非常靠近某一侧的时候呢

@万弘 2019-05-15 15:18 回复

@dxbdly 嗯?有这个性质吗?我只知道把两个三分点取在与区间的中点极为接近的位置可以使时间稳定在最坏$O(log_2n)$

@万弘 2019-05-15 15:19 回复

@dxbdly 虽然我比较喜欢这样写:

double lmid=(l+r)/2,rmid=(lmid+r)/2;

这样的复杂度也是$O(logn)$级别的,不过常数大一点

@qwaszx 2019-05-15 15:27 回复

@dxbdly 你设定的初值应该保证满足这个条件啊QAQ