Computer alle möglichen Paare von zwei Listen Effizienz

Question

Lassen Sie uns sagen, ich habe zwei Sätze von Zahlen und ich möchte alle Paare der Werte innerhalb es zu bauen. Zum Beispiel:

A = {1, 2} 
B = {3, 4} 
Out = {(1,3), (1,4), (2,3), (2,4)} 

Meine Sets haben eine Nachschlagezeit in O (1). Es sollte möglich sein, meine Ausgabe in O (| A | + | B |) zu berechnen, auch wenn die Mengen nicht die gleiche Größe haben, aber ich finde keine Lösung für diese [einfache Lösung wäre zwei foor Schleifen, aber das in O (n^2)]. Kannst du mir bitte einen Hinweis geben, wie ich das in der gegebenen Komplexität berechnen kann?

Answer 1

Nein, Sie können es nicht besser als zwei für Schleifen. Denke über diesen Weg nach. Für jedes Element in A müssen Sie B-Elemente ausgeben. Deine Laufzeit wird also immer ein Vielfaches von A * B sein.

Lassen Sie uns Ihr Beispiel ändern oben für A 3 Elemente mit Erstausstattungsreifen

A = {1, 2, 3} 
B = {3, 4} 
Out = {(1,3), (1,4), (2,3), (2,4), {3,3}, {3,4}} 

So haben Sie 6 Elemente der Ausgabe haben | A | = 3 und | B | = 2. Sie behaupten, Ihre Ausgabe sollte | A | sein + | B | Das ist 5. Daher ist Ihre ursprüngliche Annahme nicht wahr.

Ihre beste Optimierung wäre sicherzustellen, dass Sie Element der Mengen in O (1) Zeit pro Element aufzählen können.