Wie kann die Untergrenze für Matrixsortierung gefunden werden?

Question

Betrachten Sie das Problem der Sortierung einer n x n Matrix (d. H. Die Zeilen und Spalten sind in aufsteigender Reihenfolge). Ich möchte die untere und obere Grenze dieses Problems finden.

fand ich, dass es nur von O(n^2 log n) Sortieren der Elemente ist, und dann die ersten n Elemente als erste Zeile ausgibt, wird die nächsten n Elemente als die zweite Reihe, und so weiter. aber ich möchte beweisen, dass es auch Omega(n^2 log n) ist.

Nach kleineren Beispielen versuchen, ich denke, ich soll beweisen, dass, wenn ich dieses Problem lösen kann mit weniger als n^2 log(n/e) Vergleichen, wäre es die log(m!) untere Schranke für Vergleiche gegen benötigten m Elemente zu sortieren.

Irgendwelche Ideen, wie man das beweist?

Answer 1

Werfen Sie einen Blick auf .

Ihr Problem klingt, als würden Sie nur n²-Elemente statt n sortieren, daher könnte 'O (n² log n²)' beispielsweise für Mergesort gelten.

Wenn die ersten n Elemente in der ersten Zeile nicht selbst sortiert werden müssen, ist das zwar schneller, aber nicht unbedingt abhängig vom Algorithmus.

Last but not least, einige Beispiele zu testen ist kein Weg, etwas zu beweisen, besonders kleine, wo Statistiken nicht wirksam werden (, sie zeigen nicht einmal etwas an)