effizient sortierte kartesische Produkt von 2 sortierte Reihe von ganzen Zahlen

Question

Notwendigkeit Hinweise, um einen effizienten Algorithmus zu entwerfen, der die folgende Eingabe nimmt und die folgende Ausgabe ausspuckt.

Input: zwei sortierten Arrays von ganzen Zahlen A und B, die jeweils mit der Länge n

Ausgabe: Ein sortierten Array, das von Arrays A und B. kartesischen Produkt besteht

For Example: 

Input: 
A is 1, 3, 5 
B is 4, 8, 10 
here n is 3. 

Output: 
4, 8, 10, 12, 20, 24, 30, 40, 50 

Hier sind meine Versuche um dieses Problem zu lösen.

1) Da die Ausgabe n^2 ist, kann Effizienter Algorithmus nicht besser als O (n^2) Zeitkomplexität sein.

2) Zuerst versuchte ich einen einfachen aber ineffizienten Ansatz. Generieren Sie das kartesische Produkt von A und B. Es kann in O (n^2) -Zeitkomplexität erfolgen. wir müssen speichern, damit wir sortieren können. Daher auch O (n^2) Raumkomplexität. Nun sortieren wir n^2 Elemente, die nicht besser als O (n^2logn) gemacht werden können, ohne irgendwelche Annahmen über die Eingabe zu machen.

Schließlich habe ich O (n^2logn) Zeit und O (n^2) Raumkomplexitätsalgorithmus.

Es muss einen besseren Algorithmus geben, weil ich sortierte Art von Eingabearrays nicht verwendet habe.

Answer 1

Wenn es eine Lösung ist, die als O ist besser (n ² log n) es muss mehr tun, als nur die Tatsache ausnutzen, dass A und B sind bereits sortiert. Siehe meine Antwort auf this question.

---

Srikanth fragt sich, wie dies in O durchgeführt werden kann ( n) Raum (nicht in den Raum für die Ausgangszählung). Dies kann durch träges Erzeugen der Listen erfolgen.

Angenommen, wir haben A = 6,7,8 und B = 3,4,5. Zuerst wird jedes Element in A durch das erste Element in B multiplizieren, und speichert diese in einer Liste:

6 × 3 = 18, 7 x 3 = 21, 8 × 3 = 24

finden der kleinsten Element dieser Liste (6 x 3), Ausgabe, die es ersetzen es mit diesem Element in einem mal das nächste Element in B:

7 × 3 = 21, 6 × 4 = 24, 8 × 3 = 24

, um ein neues kleinstes Element dieser Liste (7 · 3), Ausgang es und ersetzen:

6 × 4 = 24, 8 x 3 = 24, 7 × 4 = 28

Und so weiter. Wir brauchen nur O (n) Platz für diese Zwischenliste, und das Finden des kleinsten Elements in jeder Stufe benötigt O (log n) Zeit, wenn wir die Liste in einer heap halten.

Answer 2

Wenn Sie einen Wert von A mit allen Werten von B multiplizieren, wird die Ergebnisliste weiterhin sortiert. In Ihrem Beispiel:

A ist 1, 3, 5

B ist 4, 8, 10

1 * (4,8,10) = 4,8,10

3 * (4,8,10) = 12,24,30

Jetzt können Sie die beiden Listen zusammenführen (genau wie in merge sort). Sie schauen sich beide Listenköpfe an und legen den kleineren in die Ergebnisliste. also hier würden Sie 4, dann 8, dann 10 usw. auswählen. result = 4,8,10,12,24,30

Jetzt machen Sie das gleiche für die Ergebnisliste und die nächste verbleibende Liste, die 4,8,10 zusammenführt , 12,24,30 mit 5 * (4,8,10) = 20,40,50.

Da das Zusammenführen am effizientesten ist, wenn beide Listen dieselbe Länge haben, können Sie dieses Schema ändern, indem Sie A in zwei Teile teilen, das Zusammenführen für beide Teile rekursiv durchführen und beide Ergebnisse zusammenführen.

Beachten Sie, dass Sie mit einem Merge-Ansatz etwas Zeit sparen können, da A nicht sortiert sein muss, sondern nur B sortiert werden muss.