Die erste Liste ist sortiert und die andere ist jetzt unsortiert. Das ist die bessere Methode, beide Listen zusammenzuführen.

Question

Ich habe eine sortierte ArrayList A und eine unsortierte ArrayList B, jetzt möchte ich Elemente von B in A zusammenführen, so dass A sortiert bleibt.

Jetzt kann ich nur zwei Möglichkeiten finden, dies zu tun.

Zuerst ein ist Arraylist B zu sortieren und dann zwei Index-Positionen eine für Arraylist A und andere für Araylist B, dann werden wir Index eins nach dem anderen bewegen B-Liste der Artikel in A. einfügen

Angenommen, die Größe von Arraylist A ist n und die Größe von Arraylist B ist m.

Reihenfolge der Komplexität wird O(m Log(m)) (zum Sortieren ArrayList B) + O(n + m) sein.

Zweiter Ansatz ist nur einen Index für ArrayListaylist B und dann Binary search verwenden Artikel von Arraylist B nach A wird

Reihenfolge der Komplexität O(Log(n) * m) zu platzieren.

Jetzt kann mir bitte jemand sagen, welchen Ansatz sollte ich wählen, auch wenn Sie an einen anderen Ansatz besser als diese beiden denken können dann bitte erwähnen.

Answer 1

Es hängt von der relativen Größe von n und m ab.

Wenn die Laufzeit des ersten Algorithmus mit Komplexität n > m*log(m)O(m*Log(m) + max(n,m)) würde von diesem linearen Term auf n (Hinweis in diesem Szenario max(n,m)=n als n>m*log(m)) dominiert werden. In diesem Fall wäre der zweite Algorithmus mit der Komplexität O(log(n) * m) besser. Der genaue praktische Abschaltpunkt würde von dem konstanten Faktor für jeden Algorithmus bestimmter Implementierungen abhängen, aber im Prinzip wird der zweite Algorithmus besser, da n in Bezug auf m größer wird und schließlich die bessere Option wird. Mit anderen Worten, für jeden möglichen Wert von m existiert ein ausreichend großer Wert für n, für den der zweite Algorithmus besser ist.

EDIT: DIE OBEN IST ZUM TEIL FALSCH

ich die gegebenen Komplexität für beide Algorithmen beantwortet unter der Annahme, aber jetzt bin ich nicht sicher, ob die Komplexität für die zweite eine richtig ist. Sie schlagen vor, jede Nummer aus der unsortierten Liste mithilfe der Binärsuche in die sortierte Liste einzufügen, aber wie genau würden Sie das tun? Wenn Sie eine verknüpfte Liste haben, können Sie keine binäre Suche durchführen. Wenn Sie ein Array haben, müssen Sie einen Teil des Arrays auf jeder Einfügung verschieben, und das ist ein linearer Overhead für jede Einfügung. Ich bin mir nicht sicher, ob es eine Möglichkeit gibt, dies mit einer komplexeren Datenstruktur zu erreichen, aber Sie können dies weder mit einer verketteten Liste noch mit einem Array tun.

Um zu verdeutlichen, wenn Sie zwei Algorithmen mit diesen Zeitkomplexitäten hatten, dann ist meine ursprüngliche Antwort gültig, aber Ihr zweiter Algorithmus hat nicht die O(m log(n)) Komplexität, die wir angenommen haben.

Answer 2

1. Ansatz: m * log (n) = O (MLGN)

2. Ansatz: m * log (m) + n + m = O (mlgm)

if n <= m { 
    1st approach 
} else { 
    2nd approach 
}