Umkehren einer Liste mit zwei Warteschlangen

12

Diese Frage ist von einer bestehenden Frage inspiriert, ob ein Stapel mit zwei Warteschlangen in amortisierter -Zeit pro Stapeloperation simuliert werden kann . Die Antwort scheint unbekannt zu sein. Hier ist eine spezifischere Frage, die dem Sonderfall entspricht, in dem alle PUSH-Operationen zuerst ausgeführt werden, gefolgt von allen POP-Operationen. Wie effizient kann eine Liste von N Elementen unter Verwendung von zwei anfänglich leeren Warteschlangen umgekehrt werden? Die rechtlichen Operationen sind:Ö(1)N

  1. Das nächste Element aus der Eingabeliste in die Warteschlange einreihen (bis zum Ende einer der Warteschlangen).
  2. Das Element am Anfang einer der beiden Warteschlangen aus der Warteschlange entfernen und erneut in die Warteschlange einreihen (bis zum Ende einer der beiden Warteschlangen).
  3. Löscht das Element am Anfang einer der Warteschlangen und fügt es der Ausgabeliste hinzu.

Wenn die Eingangsliste besteht aus Elementen , wie funktioniert die minimale Anzahl von Operationen erforderlich , um die umgekehrte Ausgabeliste zu erzeugen [ N , N - 1 , . . . , 2 , 1 ] sich verhalten? Ein Beweis, dass es schneller wächst als O ( N ), wäre besonders interessant, da es die ursprüngliche Frage verneinen würde.[1,2,...,N-1,N][N,N-1,...,2,1]Ö(N)


Update (15. Januar 2011): Das Problem kann in gelöst werden , wie in den eingereichten Antworten und ihren Kommentaren gezeigt; und eine Untergrenze von Ω ( N ) ist trivial. Kann eine dieser Grenzen verbessert werden?Ö(NLogN)Ω(N)

mjqxxxx
quelle
Zur Verdeutlichung: Beziehen Sie sich bei "dem letzten Element aus einer der Warteschlangen" auf das Element am Anfang der Warteschlange?
Peter Taylor
@ Peter: Ja, danke für die Klarstellung. Ich habe die Frage bearbeitet.
mjqxxxx
Stapeln sich sowohl die Eingabe- als auch die Ausgabeliste? Wenn ja, machen n op1s (in die gleiche Warteschlange) und n op3s den umgekehrten Weg, oder? Ich denke, mir muss etwas Wichtiges fehlen.
Jbapple
@jbapple: Nein, sie sind keine Stapel. Sie müssen Elemente in der umgekehrten Reihenfolge in die Ausgabeliste schreiben, in der sie aus der Eingabeliste gelesen wurden.
mjqxxxx

Antworten:

11

Wenn N eine Zweierpotenz ist, glaube ich, dass O (N log N) -Operationen auch für ein etwas eingeschränkteres Problem ausreichen, bei dem alle Elemente in einer der Warteschlangen beginnen und in umgekehrter Reihenfolge in einer der Warteschlangen (ohne) enden müssen die Eingabe- und Ausgabelisten).

In O (N) Schritten ist es möglich, mit allen Elementen in einer Warteschlange zu beginnen, "eins für Sie eins für mich" zu spielen, um sie in abwechselnde Untergruppen in der anderen Warteschlange aufzuteilen und sie dann alle wieder in eine Warteschlange zu verketten. In Bezug auf die binären Darstellungen der Positionen der Elemente implementiert dies eine Rotationsoperation.

In O (N) Schritten ist es auch möglich, Paare von Elementen aus einer Warteschlange zu ziehen, sie auszutauschen und dann zurückzulegen, wobei alle Paare umgekehrt werden. In Bezug auf die binären Darstellungen der Positionen der Elemente ergänzt dies das niederwertige Bit der Position.

Durch das Wiederholen von O (log N) mal einem Unshuffle und einem paarweisen Swap können wir alle Bits der binären Darstellungen der Positionen ergänzen - was dasselbe ist wie das Umkehren der Liste.

David Eppstein
quelle
Dann können Sie die Liste in eine binäre Darstellung zerlegen und Stück für Stück für einen O (n lg n) -Algorithmus umkehren, denke ich.
Jbapple
Ich dachte, man könnte auf alle N erweitern, indem man einen 2-3-Baum anstelle eines Binärbaums verwendet, aber vielleicht ist Ihre Idee einfacher. Aber wie kehrt man jedes der O (log n) Teile in O (n log n) Gesamtschritten um?
David Eppstein
Die Zeit ist O (sum (2 ^ i) lg (2 ^ i)) für i von 0 bis [lg n], was Wolfram Alpha als O (n lg n) bezeichnet: wolframalpha.com/input/?i=sum+ (2 ^ k) + log2 + (2 ^ k) + von + 0 + bis + log2 + n
jbapple
Sicher, wenn Sie jedes Stück in der Zeit umkehren können, die proportional zu seiner Länge und seinem Log ist, sind Sie fertig. Sie müssen die Teile jedoch irgendwo ablegen, nachdem Sie sie umgekehrt haben. Dies könnte es schwieriger machen, die verbleibenden Teile umzukehren.
David Eppstein
Das Problem legt eine "Ausgabeliste" an. Können wir sie dorthin bringen?
Jbapple
1

ich=0N/2-1(N-2ich-2)

Nennen wir zwei verfügbare Warteschlangen als links und rechts. Hier ist die Grundidee dieses Algorithmus mit der Annahme, dass N gerade ist:

  1. Lesen Sie Werte aus der anfänglichen Liste der Elemente und verschieben Sie alle ungeraden Zahlen in die linke Warteschlange und die geraden Zahlen in die rechte Warteschlange
  2. Einer der ersten Schritte, um den Maximalwert am schnellsten auszugeben, besteht darin, N / 2-1 Elemente aus der rechten Warteschlange in die linke zu übertragen und den obersten Wert aus der rechten Warteschlange in die Ausgabeliste einzufügen
  3. Jetzt müssen wir dasselbe für eine andere Warteschlange tun - übertragen Sie N / 2-1 Elemente aus der linken Warteschlange in die rechte und fügen Sie das oberste Element aus der linken Warteschlange in die Ausgabeliste ein
  4. Tauschen Sie die Warteschlangen aus und wiederholen Sie die Schritte 2 und 3 für N = N-2

Es ist leicht zu erkennen, wie der Algorithmus für ungerade N funktionieren sollte.

Elalfer
quelle
Sie können $ ... $ verwenden , um LaTeX-Code (abzüglich des \) einzufügen.
Mark Reitblatt