2D-Algorithmus zur Ermittlung der Spitzenwerte in O (n) -Wert-Zeit?

Question

2D-Algorithmus zur Ermittlung der Spitzenwerte in O (n) -Wert-Zeit?

8

Ich habe diesen Kurs über Algorithmen vom MIT gemacht. In der ersten Vorlesung stellt der Professor folgendes Problem vor: -

Ein Peak in einem 2D-Array ist ein Wert, bei dem alle 4 Nachbarn kleiner oder gleich sind, d. für

a[i][j] ist ein lokales Maximum,

%Vor%

Bei einem NxN-2D-Array finden Sie im Array eine Spitze .

Diese Frage kann leicht in O(N^2) time gelöst werden, indem über alle Elemente iteriert und ein Peak zurückgegeben wird.

Es kann jedoch optimiert werden, um in O(NlogN) time gelöst zu werden, indem man eine divide and conquer Lösung verwendet, wie erklärt hier .

Aber sie haben gesagt, dass es einen O(N) -Zeitalgorithmus gibt, der dieses Problem löst. Bitte schlagen Sie vor, wie wir dieses Problem in O(N) time lösen können.

PS (Für diejenigen, die Python kennen) Der Kurs hat einen Ansatz hier (Problem 1-5. Peak-Finding Proof) und lieferte auch einige Python-Code in ihren Problem-Sets. Aber der erklärte Ansatz ist absolut nicht offensichtlich und sehr schwer zu entziffern. Der Python-Code ist gleichermaßen verwirrend. Also habe ich den Hauptteil des folgenden Codes für diejenigen kopiert, die Python kennen und wissen, welcher Algorithmus aus dem Code verwendet wird.

%Vor%

algorithm language-agnostic arrays data-structures multidimensional-array

Nikunj Banka 16.04.2014, 21:15

quelle

2 Antworten

1

Hier ist der funktionierende Java-Code , der den Algorithmus von @max1000 implementiert. Der folgende Code findet eine Spitze im 2D-Array in linearer Zeit.

%Vor%

Nikunj Banka 19.04.2014 19:12

quelle

Tags und Links algorithm language-agnostic arrays data-structures multidimensional-array

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Beziehen der Gebühr aus einem Stripe-Token mithilfe der Stripe-API

score 4 · Accepted Answer

Nehmen wir an, die Breite des Arrays ist größer als die Höhe, andernfalls werden wir in eine andere Richtung aufgeteilt.
Teilen Sie das Array in drei Teile auf: zentrale Spalte, linke Seite und rechte Seite.
Gehe durch die zentrale Spalte und zwei benachbarte Spalten und suche nach dem Maximum.
- Wenn es in der zentralen Spalte ist - das ist unser Höhepunkt
- Wenn es auf der linken Seite ist, führen Sie diesen Algorithmus im Unterfeld left_side + central_column aus.
- Wenn es auf der rechten Seite ist, führen Sie diesen Algorithmus im Unterfeld right_side + central_column aus.

Warum das funktioniert:

Für Fälle, in denen das maximale Element in der zentralen Spalte ist - offensichtlich. Wenn dies nicht der Fall ist, können wir von diesem Maximum zu steigenden Elementen übergehen und werden die zentrale Reihe definitiv nicht überschreiten, so dass in der entsprechenden Hälfte definitiv ein Peak existiert.

Warum ist das O (n):

Schritt # 3 nimmt weniger als oder gleich max_dimension Iterationen und max_dimension mindestens halbiert auf jedem zwei Algorithmus-Schritten. Dies ergibt n+n/2+n/4+... was O(n) ist. Wichtiges Detail: Wir teilen uns nach der maximalen Richtung auf. Bei quadratischen Arrays bedeutet dies, dass die Splitrichtungen alternieren. Dies ist ein Unterschied zum letzten Versuch in der PDF-Datei, mit der Sie verbunden sind.

Ein Hinweis: Ich bin mir nicht sicher, ob es genau dem Algorithmus im Code entspricht, den Sie angegeben haben, es kann ein anderer Ansatz sein oder auch nicht.