Если вы не знаете, что ваши данные следуют этому определенному шаблону - увеличивайте, уменьшайте, затем увеличивайте, а затем уменьшайте - тогда лучшее, что вы можете сделать, это O (n), потому что вам придется исследовать каждый элемент в массив для определения двух высших точек.
Если вы знаете, что он определенно следует по этому шаблону, то мое лучшее предположение - это адаптация бинарного поиска, который выглядит примерно так:
- выберите среднюю точку набора данных, проверьте «градиент» - разницу между двумя последовательными значениями.
- используйте это, чтобы разделить набор данных пополам, снова проверьте средние точки двух новых пробелов; Вы хотите продолжать деление таким образом, пока не обнаружите, что у вас достаточно точек данных, чтобы у вас было вниз, а затем вверх, в указанном порядке. Между этими двумя точками находится одна из впадин, а слева от первого спада и справа от последнего - пики, которые вы ищете.
- выполнить двоичный поиск этих двух пробелов, чтобы найти фактические пики - снова, проверять два значения каждый раз, чтобы найти градиент, а не просто отбирать отдельные значения, чтобы вы могли определить, в каком направлении продолжать поиск.
Без математики я предпочитаю, что этот алгоритм в лучшем случае будет O (2log (n)), в худшем - O (n). Конечно, будет довольно редко, что вам потребуется столько времени, сколько нужно для поиска по всему набору данных, и я думаю, что вам понадобится тривиально небольшой набор данных, который займет больше времени, чем наивный поиск.