Lassen Sie uns über Algorithmen sprechen. Neulinge nehmen sie oft als etwas Schwieriges, Komplexes und Unverständliches wahr, und dies ist teilweise richtig, aber Algorithmen sind die Basis. Und je besser Sie die Grundlagen Ihrer Spezialität kennen, desto wahrscheinlicher ist es, dass Sie sich darin auszeichnen.
Heute werfen wir einen Blick auf ein schönes Algorithmusproblem. Wir werden die Leute nicht gleich zu Beginn davon abhalten, mit Algorithmen zu arbeiten, daher wird es in unserer Analyse keine sich ausbreitenden Segmentbäume, keine verschiedenen Optimierungen des Rucksackproblems oder der Einfachheit halber probabilistische Tests geben. Benutzerfreundliche Algen.
Hier ist die Herausforderung: Finden Sie den maximalen Unterschied zwischen Nachbarn.
Ein Array von N ganzen Zahlen ist gegeben. Es ist in keiner Weise bestellt und Nummern können wiederholt werden. Nehmen wir an, wir haben es sortiert und die Differenz zwischen jedem Paar aufeinanderfolgender Elemente berechnet. Es ist notwendig, den maximalen solchen Unterschied zu finden und ihn optimal zu machen.
Kompliziert? Sie können dies versuchen, bevor Sie auf "Lesen Sie mehr" klicken und dann die Lösung überprüfen.
So lass uns gehen. Maximaler Unterschied zwischen Nachbarn.
Betrachten Sie ein Beispiel:
Es sei ein Array von N = 11 Elementen angegeben.
Lassen Sie uns zunächst das Problem naiv lösen, es hilft oft. Wir können genau das tun, was das Problem von uns verlangt - die Zahlen sortieren und den Unterschied zwischen benachbarten Elementen finden. Die Komplexität der Lösung hängt davon ab, welche Sortierung wir verwenden. Wenn wirqsortodermergesort verwenden, ist die zeitliche Komplexität
. Wenn wir wissen, dass die Zahlen ziemlich dicht auf der Menge der ganzen Zahlen verteilt sind, können wir die Zählsortierung verwenden. Dann bekommen wir , wobei U die Differenz zwischen dem maximalen und dem minimalen Element ist. Der Fall ist relativ selten, aber es lohnt sich, sich an diese Möglichkeit zu erinnern.
Nach dem Sortieren erhalten wir ein Array:
Schreiben wir das Array der Unterschiede: Wir erhalten,dass die maximale Differenz 6 beträgt.Nun überlegenwir,obes möglich ist, das Problem schneller zu lösen. Wenn wir über Paare benachbarter Elemente iterieren, werden wir viele Paare mit einem kleinen Unterschied betrachten. Solche Paare können möglicherweise niemals den größten Unterschied machen. In der Tat haben wir in dem sortierten Array
Paar benachbarter Zahlen, sei die Differenz zwischen Maximum und Minimum . Dann muss der größte Unterschied mindestens haben . Diese Schätzung entspricht dem Dirichlet-Prinzip.
Wenn die Tauben in Käfige gesetzt werden und die Anzahl der Tauben größer als die Anzahl der Käfige ist, enthält mindestens einer der Käfige mehr als eine Taube.
9 Zellen enthalten 10 Tauben, nach dem Dirichlet-Prinzip enthält mindestens eine Zelle mehr als eine Taube ( Wikipedia )
Let , ... , - i-tes Element des sortierten Arrays. Dann . Wenn wir annehmen, dass das Maximum aller D [i] kleiner ist
, dann die ganze Summe ist streng kleiner als U, ein Widerspruch. Großartig, wir haben eine niedrigere Schätzung für die maximale Differenz! Versuchen wir nun, Elemente, die zu nahe beieinander liegen, irgendwie zu lokalisieren. Wir teilen das Segment vom minimalen zum maximalen Element in halbe Längenintervalle auf
. Jedes Element fällt in genau ein halbes Intervall. Wir erhalten eine Aufteilung aller Elemente in disjunkte Gruppen, die auch als Stapel bezeichnet werden.
Es ist sehr einfach zu bestimmen, in welches von ihnen das Element x gefallen ist - Sie müssen 1 + int ((x - a_min) / L) berechnen (wir nummerieren von eins), wobei a_min das minimale Element im Array A ist. Es kann in einem Durchgang gefunden werden das ursprüngliche Array. Die einzige Ausnahme ist das maximale Element. Es ist besser, Elemente mit einem solchen Wert in einem separaten Stapel zu erstellen.
Die Abbildung zeigt die Verteilung aus dem oben beschriebenen Beispiel. Lassen Sie uns dies aus Gründen der Klarheit mit unseren Händen tun:
Die Stapelverteilung erfolgt in linearer Zeit und erfordert zusätzlicher Speicher. Bitte beachten Sie, dass Artikel aus einer Charge nicht den maximalen Unterschied zwischen zwei Artikeln ergeben können. Wir haben die Größe speziell auf diese Weise ausgewählt.
Wo können zwei benachbarte Elemente sein? Natürlich in benachbarten nicht leeren Chargen! In der Abbildung können beispielsweise Elemente aus dem dritten und sechsten Stapel in einem sortierten Array hintereinander angeordnet werden, da die Stapel zwischen ihnen leer sind. Es ist klar, dass nur zwei Elemente benachbart sind - das Maximum aus der 3. Charge und das Minimum aus der 6 .. In ähnlicher Weise sind Kandidaten für ein Paar mit der maximalen Differenz das maximale Element der ersten Charge und das minimale Element der dritten Charge.
Schreiben wir alle möglichen Elementpaare auf, die den größten Unterschied bewirken können. Bezeichnen wir als min (i) - das minimale Element in der i-ten Gruppe, als max (i) - das maximale Element.
max (1) = -1 min (3) = 3
max (3) = 4 min (6) = 10
max (6) = 10 min (8) = 15
max (8) = 15 min (10) = 20
max (10) = 21 min (11) = 22
Wir haben Paare identifiziert, die eine Überlegung wert sind. In der Praxis ist es erforderlich, alle Chargen einmal zu durchlaufen, die letzte nicht leere Charge und den darin enthaltenen Maximalwert beizubehalten. Wenn wir auf den nächsten nicht leeren Stapel stoßen, werden wir das Minimum darin finden und versuchen, die Antwort zu aktualisieren.
Wir werden uns freuen - wir haben das Problem rechtzeitig gelöst .
Tatsächlich haben wir eine ziemlich bekannte Idee verwendet und tatsächlich die ersten Schritte der Taschensortierung durchgeführt. Im Original heißt sieEimersortierung.
Artikel werden in Körben angeordnet, und dann werden die Artikel in jedem Korb sortiert.
Im schlimmsten Fall funktioniert es für , aber die durchschnittliche Laufzeit mit einer ausreichenden Anzahl von Chargen und einer gleichmäßigen Verteilung der Elemente ist .
„Aber warte, was ist mit dem Fall wann? , warum hast du nicht darüber nachgedacht? “- wird der aufmerksame Leser fragen. Dieser Fall ist entartet, daher haben wir ihn nicht berücksichtigt, aber der Vollständigkeit halber tun wir es jetzt.
Wenn die Differenz zwischen dem Minimum und dem Maximum Null ist, ist auch die maximale Differenz Null. Eigentlich ist das alles.