¿Podemos obtener una lista ordenada de una matriz ordenada en

Estoy confundido. Quiero demostrar que el problema de ordenar una matriz por , es decir, las filas y columnas están en orden ascendente es . Continúo asumiendo que se puede hacer más rápido que e intento violar el límite inferior Para las comparaciones necesarias para ordenar m elementos. Tengo dos respuestas en conflicto:$n$$n$$\Omega(n^2\log n)$$n^2\log n$$\log(m!)$

1. podemos obtener una lista ordenada de los elementos de la matriz ordenada en /math/298191/lower-bound-for-matrix-sorting/298199?iemail = 1 # 298199$n^2$$O(n^2)$
2. no puede obtener una lista ordenada de la matriz más rápido que $Ω(n^2\log(n))$ /programming/4279524/how-to-sort-amxn-matrix-which-has- todas-sus-m-filas-ordenadas-y-n-columnas-ordenadas

¿Cuál es la correcta?

El límite inferior es correcto (2): no puede hacerlo mejor que y (1) es, por supuesto, incorrecto. Primero, definamos qué es una matriz ordenada: es una matriz donde los elementos de cada fila y columna se ordenan en orden creciente.$\Omega(n^2 \log n)$

Ahora es fácil verificar que cada diagonal puede contener elementos que están en cualquier orden arbitrario; solo necesita hacerlos lo suficientemente grandes. En particular, ordenar la matriz implica ordenar cada una de estas diagonales. El ° diagonal tiene entradas, y como tal,Posible pedido. Como tal, una matriz ordenada podría definir al menos diferentes ordenamientos Ahora es fácil verificar que , lo que implica que en el modelo de comparación (y como señala Jeff a continuación, en cualquier modelo de árbol de decisión binario) al menos este es un límite inferior en el tiempo de clasificación.$i$$i$$i!$$X = \prod_{i=1}^n i!$$\log_2 X = \Omega(n^2 \log n)$