这个算法的渐近时间复杂度是 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

假设我有一个整数数组 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在首尾都大1个元素，数组为H[0到m+1]，其中H[0] = H[m+1] = -infinity .因此，H[0] 和 H[m+1] 是哨兵。如果 H[p-1] ≤ H[p] ≥ H[p+1].

，则元素 p（其中 1 ≤ p ≤ n）是一个峰

我认为渐近时间复杂度是 O(log n) 但我不确定。有空请帮忙，万分感谢

Answer 1

不，这不是 O(log m)。例如，如果 H 增加，则循环执行 m 次，因为唯一的峰值是最后一个元素。所以最坏的情况是O(m).

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

这个算法的渐近时间复杂度是 O(log n)？

is the asymptotic time complexity of this algorithm O(log n)?

algorithm

big-o

asymptotic-complexity