查找多個峯在一維數組

Question

在此此MIT lecture描述和寫出在該SO question用於在1D陣列有意義發現一個峯的算法。

因此，對其分析O（log n）; 我們將陣列分成兩半

我該如何更新它才能找到所有峯值在數組中？這種複雜性會是什麼？

Answer 1

對於查找所有的峯值，你不能做任何比通過整個數組並比較每個元素與它的鄰居更好的方法。無法判斷你沒有看到的元素是否是峯值，因此你必須查看所有元素。

因此，n個元素的時間複雜度爲O（n）。