优选法

搜索

作业部落

评论地址

---

三分法

没什么好讲的，分析一波时间复杂度（网上很多是错的）
二分：

$$n*(\frac{1}{2})^k=1,k=log_{\frac{1}{2}}{\frac{1}{n}}=log_{2}{n}$$ 三分： $$n*(\frac{2}{3})^k=1,k=log_{\frac{2}{3}}{\frac{1}{n}}=log_{\frac{3}{2}}n=\frac{log_{2}{n}}{log_{2}{\frac{3}{2}}}=1.7log_{2}{n}$$
其实爬山也能做
做两道题差不多了

• [luogu3382]【模板】三分法
• [SCOI2010]传送带

华罗庚优选法（黄金优选法）

假设单峰函数答案在$(0,1)$中，$Check$步骤：
$0,0.382,0.618,1$
情况$1$:答案在$(0,0.618)$中，$0,0.236,0.382,0.618$
情况$2$:答案在$(0.382,1)$中，$0.382,0.618,0.763,1$
每次往下一层只需要新算一个量，而且每次去除的状态$>\frac{1}{3}$，是不是很棒？！

斐波那契数列的应用

$Fib_n/Fib_{n-1}=0.618$随着$n$越大越趋近
所以可以用斐波那契数列实现黄金优选
你问问度娘