Trouver pics multiples dans un tableau 1D

Question

L'algorithme décrit dans le présent et ce MIT lecture écrit dans ce SO question pour trouver un pic dans un tableau 1d est logique.

Ainsi que son analyse de O (log n); nous re divisant le tableau en deux

Comment puis-je mettre à jour pour trouver tous les pics dans le tableau? Quelle serait cette complexité?

Answer 1

Pour trouver tous les pics, vous ne pouvez faire mieux que de parcourir tout le tableau et de comparer chaque élément à ses voisins. Il n'y a aucun moyen de savoir si un élément que vous n'avez pas regardé est ou n'est pas un pic, alors vous devez tous les regarder.

Ainsi, la complexité temporelle est O (n) pour n éléments.