2D-peak-finding-Algorithmus in O(n) worst case Zeit?
Ich Tat diese natürlich auf algorithmen am MIT. In der ersten Vorlesung den professor präsentiert Folgendes problem:-
Einen peak in einem 2D-array ist ein Wert, dass alle es 4 Nachbarn sind weniger-als-oder-gleich, dh. für
a[i][j]
zu einem lokalen maximum,
a[i+1][j] <= a[i][j]
&& a[i-1][j] <= a[i][j]
&& a[i][j+1] <= a[i][j]
&& a[i+1][j-1] <= a[i][j]
Nun gegeben ein NxN 2D-array, finden Sie einen peak im array.
Diese Frage kann leicht gelöst werden, in O(N^2)
Zeit durch Iteration über alle Elemente und die Rückgabe einer Spitze.
Jedoch optimiert werden kann gelöst werden, in O(NlogN)
Zeit anhand einer Teile und herrsche-Lösung wie bereits erläutert,hier.
Aber Sie haben gesagt, dass es ein O(N)
Zeit-Algorithmus, der dieses problem löst. Bitte vorschlagen, wie können wir dieses problem lösen in O(N)
Zeit.
PS(Für diejenigen, die wissen, python) Die Kurs-Mitarbeiter erklärt hat, einen Ansatz hier (1-5 Problem. Peak-Finding-Nachweis) und auch einige python-code in Ihre problem-sets. Aber der Ansatz erklärt ist völlig nicht-offensichtliche und sehr schwer zu entziffern. Der python-code ist ebenso verwirrend. Also ich habe kopiert den wichtigsten Teil des Codes unten für diejenigen, die wissen, python und kann sagen, welcher Algorithmus verwendet wird, von dem code.
def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None):
# if it's empty, we're done
if problem.numRow <= 0 or problem.numCol <= 0:
return None
subproblems = []
divider = []
if rowSplit:
# the recursive subproblem will involve half the number of rows
mid = problem.numRow //2
# information about the two subproblems
(subStartR1, subNumR1) = (0, mid)
(subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1))
(subStartC, subNumC) = (0, problem.numCol)
subproblems.append((subStartR1, subStartC, subNumR1, subNumC))
subproblems.append((subStartR2, subStartC, subNumR2, subNumC))
# get a list of all locations in the dividing column
divider = crossProduct([mid], range(problem.numCol))
else:
# the recursive subproblem will involve half the number of columns
mid = problem.numCol //2
# information about the two subproblems
(subStartR, subNumR) = (0, problem.numRow)
(subStartC1, subNumC1) = (0, mid)
(subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))
subproblems.append((subStartR, subStartC1, subNumR, subNumC1))
subproblems.append((subStartR, subStartC2, subNumR, subNumC2))
# get a list of all locations in the dividing column
divider = crossProduct(range(problem.numRow), [mid])
# find the maximum in the dividing row or column
bestLoc = problem.getMaximum(divider, trace)
neighbor = problem.getBetterNeighbor(bestLoc, trace)
# update the best we've seen so far based on this new maximum
if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
bestSeen = neighbor
if not trace is None: trace.setBestSeen(bestSeen)
# return when we know we've found a peak
if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen):
if not trace is None: trace.foundPeak(bestLoc)
return bestLoc
# figure out which subproblem contains the largest number we've seen so
# far, and recurse, alternating between splitting on rows and splitting
# on columns
sub = problem.getSubproblemContaining(subproblems, bestSeen)
newBest = sub.getLocationInSelf(problem, bestSeen)
if not trace is None: trace.setProblemDimensions(sub)
result = algorithm4(sub, newBest, not rowSplit, trace)
return problem.getLocationInSelf(sub, result)
#Helper Method
def crossProduct(list1, list2):
"""
Returns all pairs with one item from the first list and one item from
the second list. (Cartesian product of the two lists.)
The code is equivalent to the following list comprehension:
return [(a, b) for a in list1 for b in list2]
but for easier reading and analysis, we have included more explicit code.
"""
answer = []
for a in list1:
for b in list2:
answer.append ((a, b))
return answer
- Warum Stimmen die Frage schließen?
- Nur eine zufällige peak oder alle peaks?
- Nur eine zufällige Spitze
- Eine zufällige peak ist einfach, aber sinnlos.
- Ja, es mag nutzlos sein, aber es ist eine wirklich gute Algorithmische Frage.
Du musst angemeldet sein, um einen Kommentar abzugeben.
left_side + central_column
right_side + central_column
Warum das funktioniert:
Fällen, in denen der maximale element in der mittleren Spalte - offensichtlich. Wenn nicht, können wir Schritt aus, dass die maximale Steigerung-Elemente und wird auf jeden Fall nicht über die zentrale Zeile, so dass ein Höhepunkt wird auf jeden Fall vorhanden sind, in der entsprechenden Hälfte.
Warum ist dies O(n):
Schritt #3 dauert weniger als oder gleich
max_dimension
Iterationen undmax_dimension
mindestens Hälften auf jeder Algorithmus zwei Stufen. Dies gibtn+n/2+n/4+...
dieO(n)
. Wichtiges detail: wir teilen durch die maximale Richtung. Für quadratische arrays dies bedeutet, dass die split Richtungen abwechselnd. Dies ist ein Unterschied zu den letzten versuchen in der PDF die du verlinkt wird.Anmerkung: ich bin mir nicht sicher, ob es exakt mit dem Algorithmus der code, den Sie gab, es kann oder kann nicht einen anderen Ansatz.
n+n+n+...
log(n)
Zeiten. Es istn+n/2+n/4+...<2n
T(n)=T.horiz.(n)+T.vert.(n), T.horiz(n)=T.horiz.(n/2)+O(n) and T.vert.(n)=T.vert.(n/2)+O(n)
Hier ist der funktionierende Java-code , die @maxim1000 's Algorithmus. Der folgende code findet einen Höhepunkt in der 2D-array in linearer Zeit.