读书人

查寻算法

发布时间: 2013-01-11 11:57:35 作者: rapoo

查找算法
实现一个算法,在一组随机排列的数中找到最小的一个。你能想到的最直观的算法一定是θ(n)的,想想有没有比θ(n)更快的算法?

[解决办法]
输入数据长度就是Omega(n),所以算法最低也要Omega(n)。这下限定死在这里。能有O(n)的算法说明已经是最优了。
[解决办法]
随机排列肯定是O(n)了。
[解决办法]
蒙特卡罗算法

读书人网 >软件架构设计

热点推荐