Was ist die Beziehung zwischen Zusammenführungen und Anzahl der Elemente in einem in k-Weg Merge

Question

Die Frage ist: In einer k-Weg Zusammenführung, wie viele Merge-Operation werden wir durchführen. Zum Beispiel: 2-Wege-Zusammenführung: 2 Knoten 1 zusammenführen; 3 Knoten 2 verschmelzen; 4 Knoten 3 verschmelzen. Also erhalten wir M (n) = n-1.

Was ist das M (n) wenn k ist beliebig?

Answer 1

2-Wege gehen effizientesten sind, wenn sie gleich große Blöcke verschmelzenden, so dass der effizienteste k -Wege merge bezogen auf 2-Weg ist, verschmilzt Block zuerst zu fusionieren 1 mit dem Block 2, Block 3 mit dem Block 4, usw. fusionieren Sie dann die ersten beiden resultierenden Blöcke und so weiter. Dies ist im Grunde wie mergesort arbeitet, und die Ergebnisse in O (log knk) Zeit, wobei jedes der k Blöcke enthält n Elemente annimmt. Aber es ist nur vollkommen effizient, wenn alle Bausteine ​​genau n Elemente und k ist eine Potenz von 2, also ...

Statt Durchführung k separater merge gibt, können Sie einen einzigen Durchgang verwenden, die verwendet einen Haufen auf das erste Element jedes Blocks (dh k Elemente insgesamt) enthält:

1. Lesen sie den niedrigsten Punkt aus dem Heap (O (log k ) time)
2. Schreib es out
3. es aus dem
4. Haufen entfernen Wenn der Block, dass das Element aus ist kam noch nicht erschöpft, legen Sie das nächste Stück von ihm in den Heap (wieder O (log k) Zeit).
5. Wiederholen, bis der Heap leer ist.

Wenn es insgesamt kn Artikel sind, das dauert immer O (kn log k) Zeit unabhängig davon, wie sie unter den Blöcken verteilt sind, und zwar unabhängig davon, ob k ist eine Macht von 2. Ihr Heap muss (item, block_index) Paare enthalten, so dass Sie identifizieren können, aus welchem ​​Block jedes Element stammt.

Answer 2

Ja, der Heap-Weg könnte effektiver sein. Aber was ist die Antwort auf die ursprüngliche Frage? Ich fand, dass es keine Antwort darauf geben könnte, da es vielleicht kein vollständiger k-Weg-Baum ist, also könnte 4-Wege zu 3-Wege, 2-Wege zurückgehen.

Answer 3

OK, die ursprüngliche Frage, wie angegeben zu beantworten:

k Blöcke fusionieren eine Folge von 2-Wegen mit verschmilzt immer erfordert genau k-1 verschmilzt, da unabhängig davon, welches Paar Blöcke, die Sie zu einem beliebigen Zeitpunkt zusammenführen, reduziert die Gesamtzahl der Blöcke um 1.

Wie ich in meiner ursprünglichen Antwort sagte, welche Paare von Blöcken, die Sie wählen, tut Auswirkungen auf die gesamte Zeit Komplexität -- es ist besser um Blöcke ähnlicher Größe zusammenzufassen - aber es betrifft nicht die Nummer von 2-way merge-Operationen.