Как определить нижнюю границу для сортировки матриц?

Question

Рассмотрите проблему сортировки матрицы n x n (т. Е. Строки и столбцы находятся в порядке возрастания). Я хочу найти нижнюю и верхнюю границу этой проблемы.

Я обнаружил, что это O(n^2 log n), просто сортировки элементов, а затем выводит первые n элементы в качестве первой строки, то следующий n элементы, как во втором ряду, и так далее. Однако я хочу доказать, что это также Omega(n^2 log n).

После попытки небольших примеров, я думаю, что я должен доказать, что если я могу решить эту проблему, используя менее n^2 log(n/e) сравнения, было бы нарушает log(m!) нижней границы для сравнений, необходимых для сортировки m элементов.

Любые идеи о том, как это доказать?

Answer 1

Посмотрите на http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Ваша проблема звучит так, как будто вы просто сортируете элементы n² вместо n, поэтому 'o (n² log n²)' может быть действительным для mergesort, например.

Если первые n элементов в первой строке не нужно сортировать сами, это может быть быстрее, но не обязательно, это зависит от алгоритма.

Последнее, но не менее важное: попытка некоторых примеров не доказывает что-то, особенно мелкие, где статистика не вступает в силу (они даже не указывают ничего)