Bisakah kita mendapatkan daftar yang diurutkan dari matriks yang diurutkan dalam

Saya bingung. Saya ingin membuktikan bahwa bahwa masalah menyortir oleh n matriks yaitu baris dan kolom dalam urutan menaik adalah Ω ( n 2 log n ) . Saya melanjutkan dengan mengasumsikan bahwa itu dapat dilakukan lebih cepat daripada n 2 log n dan mencoba untuk melanggar log ( m ! ) Batas bawah untuk perbandingan yang diperlukan untuk mengurutkan elemen m. Saya punya dua jawaban yang saling bertentangan:$n$$n$$\Omega(n^2\log n)$$n^2\log n$$\log(m!)$

1. kita bisa mendapatkan daftar elemen yang diurutkan dari matriks yang diurutkan dalam O ( n 2 ) /math/298191/lower-bound-for-matrix-sorting/298199?iemail=1 # 298199$n^2$$O(n^2)$
2. Anda tidak bisa mendapatkan daftar yang diurutkan dari matriks lebih cepat dari /programming/4279524/how-to-sort-amxn-matrix-which-has-all- nya-m-rows-sortir-dan-n-kolom-diurutkan$Ω(n^2\log(n))$

Yang mana yang benar?

$\Omega(n^2 \log n)$

$i$$i$$i!$$X = \prod_{i=1}^n i!$$\log_2 X = \Omega(n^2 \log n)$, menyiratkan bahwa dalam model perbandingan (dan seperti yang ditunjukkan Jeff di bawah, dalam model pohon keputusan biner apa pun), setidaknya ini adalah batas bawah pada waktu penyortiran.