Làm thế nào có thể tìm thấy giới hạn dưới để phân loại ma trận?

Question

Xem xét vấn đề phân loại ma trận n x n (nghĩa là các hàng và cột được sắp xếp theo thứ tự tăng dần). Tôi muốn tìm giới hạn dưới và trên của vấn đề này.

Tôi thấy rằng đó là O(n^2 log n) bằng cách chỉ phân loại các phần tử và sau đó xuất các thành phần n đầu tiên làm hàng tiếp theo, n thành phần tiếp theo làm hàng thứ hai, v.v. tuy nhiên tôi muốn chứng minh rằng nó cũng là Omega(n^2 log n). Sau khi thử các ví dụ nhỏ hơn, tôi nghĩ tôi nên chứng minh rằng nếu tôi có thể giải quyết vấn đề này bằng cách sử dụng ít hơn n^2 log(n/e) so sánh, nó sẽ vi phạm giới hạn dưới của log(m!) để so sánh cần thiết để sắp xếp các yếu tố m.

Bất kỳ ý tưởng nào về cách chứng minh điều đó?

Answer 1

Có giao diện trên http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Vấn đề của bạn có vẻ như bạn chỉ sắp xếp các phần tử n² thay vì n, do đó 'O (n² log n²)' có thể hợp lệ để hợp nhất ví dụ.

Nếu n thành phần đầu tiên trong hàng đầu tiên không cần phải tự sắp xếp, nó có thể nhanh hơn, nhưng không nhất thiết, nó phụ thuộc vào thuật toán.

Cuối cùng nhưng không kém phần quan trọng, hãy thử một số ví dụ là không có cách nào chứng minh điều gì đó, đặc biệt là các thống kê nhỏ không có hiệu lực (họ thậm chí không chỉ ra điều gì)