难以理解峰值查找算法的差异

Question

这是一个关于一维峰值查找的问题（如果元素比数组中的邻居大，它就是一个峰值）。我正在看麻省理工学院的开放式课程讲座，他谈到了一个天真的解决方案：从索引0开始，一直到最后。

然后他说分而治之的解决方案要好得多。我不明白怎么会这样。这难道不是根据数组的内容做出假设吗？如果只是随机数，那又有什么区别呢？

讲师说他写了一个Python脚本，朴素的解决方案花了13秒，而log(N)解决方案只花了.001秒。我写了一些C#代码，朴素算法在前20个左右的元素中找到一个峰值，运行需要一毫秒的时间。我是不是漏了什么？

以下是本次讲座的PDF摘要:http://ocw.mit.edu/courses/electrice-engineering-and-computer-science/6-006-Introduction-to-algorithms-Fall-2011/lecture-videos/mit6_006F11_LEC01.PDF

Answer 1

与峰有关的是，峰总是存在，要么在中间，要么在左半边，要么在右半边。

假设您发现中间的元素是5，左边的元素是6。那么6是一个峰值吗？否，如果6的左元素是更大的元素，假设7。那么7是一个峰值吗？否，如果7的左元素是更大的元素，假设8。您可以继续这个过程，直到您找到一个峰值或您到达最左边的元素。在后一种情况下，您会得到一个不断增加的数字序列，因此最左边的元素是一个峰值。

所以如果你发现中间的元素比左边的邻居小，那么你肯定知道在左半部寻找一个峰值。你不关心右半部分是否有另一个峰值，不管这个数字的分布是多么随机。如果中间的元素比它的右邻居小，这也是一样的。

就实现的运行时间而言。朴素算法将很快完成，如果它发现一个峰值附近在开始。取一个从1到1000000的序列进行测试，因为峰值位于最后一个元素。