Längste aufsteigende Teilfolge (LIS)
Wählen Sie Zahlen aus einer Liste, von links nach rechts, jede größer als die vorige. Wie lang kann eine solche Kette werden? Die Frage ist einfach genug für ein Rätselbuch, und ihre Antwort verbindet ein Kartenspiel, eine klassische Tabelle der dynamischen Programmierung und eines der schönsten Ergebnisse über zufällige Mischungen.
Das Problem
Gegeben ist eine Liste von Zahlen. Eine Teilfolge behält einige davon in ihrer ursprünglichen Reihenfolge. Sie ist aufsteigend, wenn jeder Wert größer ist als der vorige. Die längste aufsteigende Teilfolge, kurz LIS, ist die längste solche Auswahl. Eine Liste mit n Werten hat 2ⁿ Teilfolgen, deshalb klappt es nur bei sehr kurzen Listen, alle zu prüfen.
Die Tabelle
Sei len[i] die Länge der längsten aufsteigenden Teilfolge, die genau an Position i endet. Sie ist 1 für den Wert allein oder 1 + len[j] für eine frühere Position j mit kleinerem Wert, je nachdem, was am größten ist. Jede Position blickt auf alle früheren zurück, also braucht die Tabelle n·(n − 1)/2 Vergleiche. Die Lösung ist das größte len[i], und wenn man notiert, welches j jedes len[i] geliefert hat, kann man die Teilfolge zurücklesen.
Ein Beispiel
Nehmen Sie 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Position für Position sind die Längen 1, 2, 1, 1, 3, 2, 3, 4, 3 und 5: Die 20 verlängert 3, 10; die 4 verlängert die 3; die 6 verlängert die 4, die 7 die 6 und die 9 die 7. Das Zurücklesen ab der 9 ergibt 3, 4, 6, 7, 9, eine aufsteigende Teilfolge der Länge 5.
Schneller: Patience Sorting
Verteilen Sie die Werte wie Karten auf Stapel: Jeder Wert kommt auf den Stapel ganz links, dessen oberste Karte nicht kleiner ist als er, oder er beginnt rechts einen neuen Stapel. Die Anzahl der Stapel ist die Länge der LIS. Weil die obersten Karten der Stapel immer sortiert sind, lässt sich der richtige Stapel durch binäre Suche finden, sodass das ganze Verfahren O(n log n) Schritte braucht. Es ist nach dem Kartenspiel Patience benannt, dem es ähnelt.
Ein wenig Mathematik
1935 bewiesen Paul Erdős und George Szekeres, dass jede Liste von n² + 1 verschiedenen Zahlen eine aufsteigende oder eine absteigende Teilfolge der Länge n + 1 enthält. Stanislaw Ulam fragte 1961, wie lang die LIS einer zufälligen Mischung von n Zahlen ist. Die Antwort, nahe bei 2√n für großes n, wurde 1977 von Anatoly Vershik und Sergei Kerov sowie von Ben Logan und Larry Shepp geklärt, und 1999 fanden Jinho Baik, Percy Deift und Kurt Johansson die genaue Form ihrer Schwankungen: die Tracy–Widom-Verteilung aus der Theorie der Zufallsmatrizen.
Selbst ausprobieren
Öffnen Sie die App und drücken Sie Schritt. Die orange Spalte ist die Position, die gerade berechnet wird, und die blaue Spalte die frühere Position, mit der sie verglichen wird. Die Zeile Länge wächst, wenn längere Ketten gefunden werden, die Zeile Folgt auf merkt sich, woher sie kommen, und am Ende wird die Lösung in Orange zurückgelesen und unter der Tabelle angezeigt.
Häufig gestellte Fragen
Welche Zeitkomplexität hat die LIS?
O(n²) mit der Tabelle, weil jede Position jede frühere betrachtet, und O(n log n) mit Patience Sorting und binärer Suche. Beide brauchen O(n) Speicher.
Wie finde ich die längste nicht fallende Teilfolge?
Lassen Sie einen Wert auch auf einen gleichen folgen: Vergleichen Sie mit ≤ statt mit <. Aktivieren Sie in der App Gleiche Werte erlauben. Beim Patience Sorting legen Sie jeden Wert auf den Stapel ganz links, dessen oberste Karte echt größer ist.
Was ist die längste absteigende Teilfolge?
Dasselbe Problem mit umgedrehtem Vergleich, oder die LIS der Liste, in der jeder Wert negiert ist. Nach dem Satz von Erdős–Szekeres hat eine genügend lange Liste immer eine lange aufsteigende oder eine lange absteigende Teilfolge.
Wie lang ist die LIS einer zufälligen Liste?
Bei einer zufälligen Mischung von n verschiedenen Zahlen ungefähr 2√n für großes n. Die Korrektur wächst wie die sechste Wurzel aus n, sodass der Durchschnitt bei tausend Zahlen etwa 58 beträgt, etwas weniger als 2√1000 ≈ 63.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Längste aufsteigende Teilfolge ausprobieren