Ein lokales Maximum in einem 2D-Array kann als ein Wert definiert werden, so dass alle seine 4 Nachbarn kleiner oder gleich sind, dh dass a[i][j] ein lokales Maximum ist,
Ich wurde gebeten, alle lokalen Maxima in einem gegebenen 2D-Array zu finden.
Der naive Weg wäre, einfach alle Elemente durchzugehen und zu prüfen, ob jedes Element ein lokales Maximum ist oder nicht. Dies wäre O (n ^ 2). Ich habe das Gefühl, dass man es nicht besser machen kann, obwohl mein Freund darauf besteht, dass ein asymptotisch besserer Algorithmus existiert. Irgendwelche Hinweise?
Ich habe an die Grenzen von Divide and Conquer gedacht, aber ich glaube, dass es unmöglich wäre, alle lokalen Maxima zu erkennen, ohne alle Zahlen durchzugehen, was notwendigerweise O (n ^ 2) wäre. Habe ich recht oder verpasse ich etwas?
Ich bin mir ziemlich sicher, dass dies nicht in weniger als 0 (n ^ 2) Vergleichen gelöst werden kann. Nehmen Sie eine Schachbrett 2d Matrix an, in der alle weißen Quadrate 1 und schwarze 0 sind. Sie wird O (n ^ 2) Lösungen haben und jede Lösung erfordert mindestens einen Vergleich.
Nur ein Heads-up, lokale Maxima oder Minima eines 2D-Gitters können in O (nlgn) -Zeit mit einer Divide-and-Conquer-Strategie berechnet werden. Dies ist eine etwas bessere Zeitgrenze als der Brute-Force-Algorithmus, der in der O (n ^ 2) -Zeitkomplexitätsklasse enthalten ist. Darüber hinaus können Verbesserungen am Divide and Conquer-Algorithmus vorgenommen werden, um einen O (n) -Algorithmus für die 2D-Gitterextrembefunde zu erhalten.
Sehen Sie sich diese Hinweise zur Theorie hinter solchen Peak-Picking-Algorithmen an (ich bin mir sicher, dass es mehr Materialien gibt):
Sofern Ihr Array nicht quadratisch ist, ist Ihre Lösung tatsächlich O(I * J) nicht O( n^2 ) . Streng genommen haben Sie nur N Elemente in Ihrem 2d Array, daher ist diese Lösung O(N) . Der einzige Weg, wie es sein könnte O( n^2 ) ist, wenn das Array so quadratisch war, dass I = J = N .
Da der Vergleich <= und nicht < ist, müssen Sie immer noch das nächste Element überprüfen. Alle Verknüpfungen, die Sie versuchen, sind wahrscheinlich prozessorspezifisch.
Der schlimmste Fall ist, dass das gesamte Array ein lokales Maximum ist, weil das Das gesamte Array ist gleich.
Sie müssen also jedes Element einmal besuchen, um es zu O(N)
Um die Leistung in der realen Welt zu verbessern, müssten Sie Zeiger verwenden, um auf Ihr Array zuzugreifen, da in den meisten Sprachen 2D-Arrays erheblich schlechter als 1D-Arrays sind.
SIE MÜSSEN NICHT JEDES ELEMENT BESUCHEN:
Alles, was Sie tun müssen, ist das Gitter zu visualisieren und Sie werden sehen, dass dies in viel weniger als einer flachen n ^ 2 (oder I * J) gelöst werden kann. Hier sind die Optimierungen nach Level:
1] für eine I * J-Matrix benötigen Sie nur die Suche (I-2) * (J-2). Warum? Die Grenzen können wegen der undefinierten Elemente keine Maxima sein:
%Vor%Bei einem Raster von 10 mal 12 betrachten wir also nicht alle 120 Elemente, sondern 80 Elemente.
2] Wenn Gitter [I] [J] ein Maximum ist, können wir alle Zellen, die an [I] [J] angrenzen, überspringen, während wir die Suche fortsetzen. Dies wird die Anzahl der zu vergleichenden Elemente weiter reduzieren.
Daher lautet die Antwort nein, Sie müssen nicht jedes Element besuchen.
Die obigen Antworten verteidigen nur ein mathematisches Modell.
Das ergibt sich aus einer vereinfachten Sicht auf das Problem.
Wenn Sie als Programmierer arbeiten, sollten Sie wissen, was ein Prozessor tun kann. Und Sie sollten wissen, dass Code in einem Thread ausgeführt wird. Sie sollten sich fragen, ob eine Aufgabe in kleineren Aufgaben unterteilbar ist, so dass Sie in der Lage sind, Multi-Threaded zu bearbeiten und eine Ausführungsgeschwindigkeit von 1 / Gesamt-Threads zu erreichen.
Der Code dafür hängt von der Sprache ab, daher gebe ich hier kein Beispiel.