Come si può trovare il limite inferiore per l'ordinamento matriciale?

Question

Considerare il problema di ordinare una matrice n x n (vale a dire che le righe e le colonne sono in ordine crescente). Voglio trovare il limite inferiore e superiore di questo problema.

ho trovato che è O(n^2 log n) semplicemente classificare gli elementi e quindi in uscita i primi n elementi come la prima riga, entro n elementi come la seconda fila, e così via. tuttavia voglio provare che è anche Omega(n^2 log n).

Dopo aver provato esempi più piccole, penso che dovrei dimostrare che se riesco a risolvere questo problema utilizzando meno di n^2 log(n/e) confronti, sarebbe viola la log(m!) limite inferiore per i confronti necessari per ordinare m elementi.

Qualche idea su come dimostrarlo?

Answer 1

Dai uno sguardo allo http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Il tuo problema sembra come se stessi semplicemente n² elementi invece di n, quindi 'O (n² log n²)' potrebbe essere valido per esempio per mergesort.

Se i primi n elementi nella prima riga non devono essere ordinati da soli, potrebbe essere più veloce, ma non necessariamente, dipende dall'algoritmo.

Ultimo ma non meno importante, provare alcuni esempi non è in alcun modo provare qualcosa, specialmente quelli piccoli in cui le statistiche non hanno effetto (, non indicano nemmeno qualcosa)