ist die asymptotische Zeit Komplexität dieses Algorithmus O (log n)?

Question

Der psuedocode Algorithmus p zu finden ist:

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 

Lassen Sie uns sagen, dass ich ein Array H [1 bis m] haben von int-Werte, wobei "p" das Element Spitze ist, wenn:

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. 

Grundsätzlich , H [p] ist der Peak, wenn er größer oder gleich seinen Nachbarelementen ist.

Es wird angenommen, dass das Array H um 1 Element am Anfang und am Ende größer ist, das Array ist H [0 bis m + 1], wobei H [0] = H [m + 1] = -infinity. Daher sind H [0] und H [m + 1] Sentinels. Dann ist ein Element p mit 1 ≤ p ≤ n ein Peak, wenn H [p-1] ≤ H [p] ≥ H [p + 1].

Ich denke, die asymptotische Zeit Komplexität ist O (log n), aber ich bin mir nicht sicher. Bitte helfen Sie, wenn Sie können, vielen Dank.

Answer 1

Nein, es ist nicht O (log m). Wenn beispielsweise H zunimmt, führt die Schleife m mal aus, da der einzige Peak das letzte Element ist. Also ist der schlimmste Fall O (m).

Eine O (log m) -Lösung sieht folgendermaßen aus: Um einen Peak in einem Array zu finden, dessen Endelemente kleiner sind als ihre Nachbarn, betrachten Sie das mittlere Element des Arrays. Wenn es ein Peak ist, dann hör auf. Andernfalls, wenn es kleiner ist als das Element auf der linken Seite, finde einen Peak in der linken Hälfte des Arrays. Wenn es kleiner ist als das Element auf der rechten Seite, finden Sie eine Spitze in der rechten Hälfte des Arrays. Es muss kleiner sein als das eine oder das andere, da es kein Peak ist. Dies halbiert ungefähr die Größe des Arrays jedes Mal, und es wird garantiert beendet, da sobald das Array die Größe 3 erreicht, das mittlere Element garantiert ein Peak ist, da die Endelemente (konstruktiv) kleiner sind als ihr Nachbar - das mittlere Element.