Peut-on obtenir une liste triée à partir d'une matrice triée en

Je suis confus. Je veux prouver que le problème du tri d'une matrice $n$ par $n$ c'est-à-dire que les lignes et les colonnes sont en ordre croissant est $\Omega(n^2\log n)$ . Je continue en supposant que cela peut être fait plus rapidement que $n^2\log n$ et j'essaie de violer la borne inférieure $\log(m!)$ Pour les comparaisons nécessaires pour trier m éléments. J'ai deux réponses contradictoires:

1. nous pouvons obtenir une liste triée des $n^2$ éléments de la matrice triée dans $O(n^2)$ /math/298191/lower-bound-for-matrix-sorting/298199?iemail=1 # 298199
2. vous ne pouvez pas obtenir une liste triée de la matrice plus rapidement que /programming/4279524/how-to-sort-amxn-matrix-which-has- tout-ses-m-lignes-triées-et-n-colonnes-triées$Ω(n^2\log(n))$

Laquelle a raison?

La borne inférieure est correcte (2) - vous ne pouvez pas faire mieux que et (1) est bien sûr faux. Permet de définir d'abord ce qu'est une matrice triée - c'est une matrice où les éléments de chaque ligne et colonne sont triés dans l'ordre croissant.$\Omega(n^2 \log n)$

Il est maintenant facile de vérifier que chaque diagonale peut contenir des éléments qui sont dans n'importe quel ordre arbitraire - il suffit de les rendre suffisamment grands. En particulier, le tri de la matrice implique de trier chacune de ces diagonales. La ème diagonale a entrées, et en tant que tellecommande possible. Ainsi, une matrice triée pourrait définir au moins différentes commandes. Il est maintenant facile de vérifier que , ce qui implique que dans le modèle de comparaison (et comme Jeff le souligne ci-dessous, dans tout modèle d'arbre de décision binaire) au moins c'est une borne inférieure sur le temps de tri.i i ! X = ∏ n i = 1 i ! log 2 X = Ω ( n 2 log n $i$$i$$i!$$X = \prod_{i=1}^n i!$$\log_2 X = \Omega(n^2 \log n)$