该算法的渐近时间复杂度是O（log n）？

Question

查找p的伪码算法为：

peakreturn(H)
for p=1 to m //m is the length of H
    if H[p-1] ≤ H[p] and H[p] ≥ H[p+1] then return p
return nil // only returns this if there is no peak

假设我有一个int值的数组H[1到m]，其中“p”是峰值元素，如果：

H[p] ≥ H[p+1] if p = 1,
H[p-1] ≤ A[p] ≥ H[p+1] if 1 < p < m,
H[p] ≥ H[p-1] if p = m.

基本上，如果H【p】大于或等于其相邻元素，则H【p】为峰值。

假设数组H在开始和结束时都大于1个元素，数组为H[0到m 1]，其中H[0]=H[m 1]=无穷大。因此，H[0]和H[m 1]是哨兵。然后是元素p，其中1≤ p≤ n、 是一个峰值，如果H【p-1】≤ H【p】≥ H【p 1】。

我认为渐近时间复杂度是O（log n），但我不确定。如果可以的话，请帮忙，非常感谢。

Answer 1

不，不是O（log m）。例如，如果H正在增加，那么循环执行m次，因为唯一的峰值是最后一个元素。所以最坏的情况是O（m）。

O（log m）的解决方案如下所示：要在数组中找到末端元素小于其邻居的峰值，请考虑数组的中间元素。如果它是峰值，则停止。否则，如果它小于其左侧的元素，请在数组的左半部中找到一个峰值。如果它小于其右侧的元素，请在数组的右半部中找到一个峰值。它必须小于一个或另一个，因为它不是峰值。这几乎每次都将数组的大小减半，并且保证终止，因为一旦数组达到大小3，中间元素就保证是峰值，因为结束元素（通过构造）小于它们的邻居——中间元素。