W jaki sposób można znaleźć dolną granicę sortowania macierzy?

Question

Rozważ problem sortowania macierzy n x n (tzn. Wiersze i kolumny są w porządku rosnącym). Chcę znaleźć dolną i górną granicę tego problemu.

okazało się, że jest to po prostu O(n^2 log n) sortowania elementów, a następnie wyprowadzanie pierwszego n elementy jak w pierwszym rzędzie, kolejne n elementy jak w drugim rzędzie, i tak dalej. jednak chcę udowodnić, że jest również Omega(n^2 log n).

Po wypróbowaniu mniejszych przykładów, myślę, że powinienem udowodnić, że jeśli mogę rozwiązać ten problem przy użyciu mniej niż n^2 log(n/e) porównań, prawda narusza log(m!) dolna granica dla porównań potrzebnych do sortowania m elementy.

Jakieś pomysły, jak to udowodnić?

Answer 1

Spójrz na http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Twój problem brzmi, jakbyś sortował n² elementów zamiast n, dlatego "O (n² log n²)" może być ważne na przykład w mergesort.

Jeśli pierwszych n elementów w pierwszym rzędzie nie trzeba samemu sortować, może być szybszy, ale niekoniecznie zależy od algorytmu.

Wreszcie, próbując przykładów, nic nie dowodzi, zwłaszcza te małe, w których statystyki nie działają (nie są nawet wskazaniem).