は、このアルゴリズムの漸近時間の複雑さです。O（log n）？ Pを見つける

Question

擬似コードアルゴリズムは次のとおりです。

基本的に

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. 

：

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 

はのがあれば、私は "p" は、ピーク要素であるint型の値の配列H [mまで1]を持っているとしましょうH [p]は、その隣接要素よりも大きいかまたは等しい場合のピークである。

ここで、H [0] = H [m + 1] = - 極限の場合、配列Hは最初と最後で1要素だけ大きいと仮定し、配列はH [0~m + 1]です。したがって、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になると、末尾の要素が隣接する要素よりも小さいため、中間の要素がピークであることが保証されるので、終了することが保証されます - 中間要素。