查找多个峰在一维数组

Question

在此此MIT lecture描述和写出在该SO question用于在1D阵列有意义发现一个峰的算法。

因此，对其分析O（log n）; 我们将阵列分成两半

我该如何更新它才能找到所有峰值在数组中？这种复杂性会是什么？

Answer 1

对于查找所有的峰值，你不能做任何比通过整个数组并比较每个元素与它的邻居更好的方法。无法判断你没有看到的元素是否是峰值，因此你必须查看所有元素。

因此，n个元素的时间复杂度为O（n）。