Ich habe die Aufgabe, einen Algorithmus zu schreiben (nicht in einer bestimmten Sprache, nur Pseudo-Code), der eine Matrix [Größe: M x N] erhält, die so sortiert ist, dass alle Zeilen sortiert sind und alle Seine Spalten werden einzeln sortiert und finden innerhalb dieser Matrix einen bestimmten Wert. Ich muss den zeiteffizientesten Algorithmus schreiben, den ich mir vorstellen kann.
Die Matrix sieht ungefähr so aus:
%Vor%Meine Idee ist es, bei der ersten Zeile und der letzten Spalte zu beginnen und einfach den Wert zu überprüfen. Wenn er kleiner ist, gehe nach links und mache so weiter, bis der Wert gefunden wird oder bis die Indizes außerhalb der Grenzen liegen (falls der Wert nicht existiert). Dieser Algorithmus arbeitet mit linearer Komplexität O (m + n). Mir wurde gesagt, dass dies mit einer logarithmischen Komplexität möglich ist. Ist es möglich? und wenn ja, wie?
Ihre Matrix sieht so aus:
%Vor%und hat folgende Eigenschaften:
%Vor% So ist der Wert in der niedrigsten rechten Ecke (zB i ) immer der größte in der gesamten Matrix
und diese Eigenschaft ist rekursiv, wenn Sie die Matrix in 4 gleiche Teile teilen.
So könnten wir versuchen, die binäre Suche zu verwenden:
Daher könnte der Algorithmus so aussehen:
%Vor%Dies sieht für mich wie ein O (log n) aus, wobei n die Anzahl der Elemente in der Matrix ist. Es ist eine Art binäre Suche, aber in zwei Dimensionen. Ich kann es nicht formell beweisen, sondern ähnele einer typischen binären Suche.
und so sieht die Beispieleingabe aus? Sortiert nach Diagonalen? Das ist eine interessante Art, um sicher zu sein.
Da die folgende Zeile möglicherweise einen Wert aufweist, der niedriger ist als jeder Wert in dieser Zeile, können Sie von einer bestimmten Datenzeile nichts annehmen.
Ich würde (wenn ich dazu aufgefordert würde, dies über eine große Eingabe zu tun) die Matrix in eine list-struct lesen, die die Daten als ein Paar eines Tupels und die mxn-Koordinate als Teil des Tupels und dann als Quicksort verwendet Matrix einmal, dann finden Sie es nach Wert.
Wenn der Wert jedes einzelnen Speicherorts eindeutig ist, werfen Sie die MxN-Daten in ein auf den Wert geschriebenes Wörterbuch und springen dann zum Wörterbucheintrag des MxN, basierend auf dem Schlüssel der Eingabe (oder dem Hash des Schlüssels) der Eingabe).
BEARBEITEN:
Beachten Sie, dass die obige Antwort gültig ist, wenn Sie mehr als einmal durch die Matrix schauen. Wenn Sie es nur einmal analysieren müssen, ist dies so schnell wie möglich:
%Vor%Offensichtlich sollte mein Kommentar zu der Frage auch hier untergehen: |
@sagar, aber das ist nicht das Beispiel des Professors. Sonst hatte er die schnellste Methode oben (überprüfe das Ende der Zeile zuerst, dann fahre fort) zusätzlich, das Ende der mittleren Zeile zuerst zu prüfen wäre schneller, ein bisschen eine binäre Suche.
Das Ende jeder Zeile zu überprüfen (und am Ende der mittleren Zeile zu beginnen), um eine Zahl zu finden, die höher ist als die in einem Array im Speicher überprüfte Zahl, wäre am schnellsten finde es.
in Protokoll M können Sie eine Reihe von Zeilen erhalten, die das Ziel enthalten können (binäre Suche nach dem ersten Wert der Zeilen, binäre Suche nach dem letzten Wert der Zeilen, nur die Zeilen, deren erstes & lt; = Ziel und letztes & gt; = Ziel) zwei binäre Suchen ist immer noch O (log M)
dann in O (log N) können Sie jede dieser Reihen erforschen, mit wiederum einer binären Suche!
das macht es O (logM x logN)
Tadaaaa
Wie wäre es, wenn die Diagonale herauskommt, dann binäre Suche über die Diagonale, beginnend unten rechts, ob es oben ist, wenn ja, nehmen Sie die diagonale Array-Position als Spalte, wenn nicht, dann prüfen Sie, ob sie darunter ist. jedes Mal, wenn Sie eine binäre Suche in der Spalte ausführen, sobald Sie einen Treffer auf der Diagonale haben (indem Sie die Array-Position der Diagonalen als Spaltenindex verwenden). Ich denke, das ist, was von @ user942640
angegeben wurdeSie können die Laufzeit der oben genannten und wenn erforderlich (zu einem bestimmten Zeitpunkt) die Algo zu einer binären Suche auf der ersten diagonalen Array (das ist unter Berücksichtigung seiner n * n Elemente und bekommen x oder y Länge ist O (1) wie x.length = y.length selbst auf einer Million * Millionen binär die Diagonale suchen, wenn es weniger als die Hälfte der Diagonale zurück ist, wenn es nicht kleiner ist als die binäre Suche zurück dorthin, wo du warst ( das ist eine kleine Änderung am Algo, wenn man eine binäre Suche entlang der Diagonale durchführt. Ich denke, die Diagonale ist besser als die binäre Suche in den Zeilen, ich bin gerade zu müde, um mir die Mathe anzusehen:)
Übrigens glaube ich, dass die Laufzeit etwas anders ist als die Analyse, die Sie in Bezug auf den besten / schlechtesten / durchschnittlichen Fall und die Zeit gegen die Speichergröße beschreiben würden. Die Frage wäre also besser wie in "Was ist das Beste?" Laufzeit im schlimmsten Fall Analyse ', denn im besten Fall könnten Sie einen brutalen linearen Scan und das Element könnte in der ersten Position sein, und das wäre eine bessere' Laufzeit 'als binäre Suche ...
Hier ist eine untere Grenze von n . Beginnen Sie mit einem unsortierten Array A der Länge n . Konstruiere eine neue Matrix M nach folgender Regel: Die sekundäre Diagonale enthält das Array A, alles darüber ist minus unendlich, alles darunter ist plus unendlich. Die Zeilen und Spalten sind sortiert, und die Suche nach einem Eintrag in M entspricht der Suche nach einem Eintrag in A.
Dies ist im Sinne von Michals Antwort (von der ich die nette Grafik stehlen werde).
Matrix:
%Vor%Min und Max sind die kleinsten bzw. größten Werte. "Mitte" ist nicht unbedingt der Durchschnitt / Median / was auch immer.
Wir wissen, dass der Wert in der Mitte & gt; = alle Werte in Quadrant II und & lt; = alle Werte in Quadrant IV ist. Wir können solche Ansprüche für die Quadranten I und III nicht geltend machen. Wenn wir rekrutieren, können wir auf jeder Ebene einen Quadranten eliminieren.
Wenn also der Zielwert kleiner als Mitte ist, müssen wir die Quadranten I, II und III suchen. Wenn der Zielwert größer als Mitte ist, müssen wir die Quadranten I, III und IV suchen.
Der Platz wird bei jedem Schritt auf 3/4 reduziert:
n * (3/4) x = 1
n = (4/3) x
x = log 4/3 (n)
Logarithmen unterscheiden sich durch einen konstanten Faktor, also ist dies O (log (n)).
%Vor%Das ist eine falsche Antwort
Ich bin mir wirklich nicht sicher, ob eine der Antworten die optimale Antwort ist. Ich bin dabei.
Ich denke, die Zeitkomplexität ist 2 * (log m + log n).
Sie können die Konstante reduzieren, wenn das Eingabearray ein Quadrat (n * n) ist, durch binäre Suche entlang der Diagonale.
Tags und Links language-agnostic search time-complexity matrix big-o