Можем ли мы получить отсортированный список из отсортированной матрицы в

9

Я смущен. Я хочу доказать, что это проблема сортировкиN по n матрица, т.е. строки и столбцы в порядке возрастания Ω(n2logn), Я исхожу из предположения, что это можно сделать быстрее, чемn2logn и попытаться нарушить log(m!) нижняя граница для сравнений, необходимых для сортировки m элементов. У меня есть два противоречивых ответа:

  1. мы можем получить отсортированный список n2 элементы из отсортированной матрицы в O(n2) /math/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
  2. Вы не можете получить отсортированный список из матрицы быстрее, чем /programming/4279524/how-to-sort-amxn-matrix-which-has- все его-м-строки отсортированные-и-н-колонки-отсортированоΩ(n2log(n))

Какой из них прав?

user2038833
источник
6
Кроме того, меня раздражает, когда мы видим утверждения, что «сортировка - это », но в которой не указывается модель ввода и модель вычислений. Сортировка сравнения . Сортировка, как правило, может быть быстрее, чем, например, для строк (если - общая длина ввода) или целых чисел (в некоторых моделях вычислений, которые допускают целочисленные арифметические операции с постоянным временем). Ω(nlogn)Ω(nlogn)n
Дэвид Эппштейн
3
Чтобы быть еще более педантичным: сортировка сравнения не является , потому что сортировка сравнения не является функцией от до . Для сортировки требуется время в любой бинарной модели дерева решений (не только для сравнения). Ω(nlogn)RRΩ(nlogn)
Джефф

Ответы:

15

Нижняя граница верна (2) - вы не можете сделать это лучше, чем Ω(n2logn)и (1), конечно, неправильно. Давайте сначала определим, что такое отсортированная матрица - это матрица, в которой элементы в каждой строке и столбце сортируются в порядке возрастания.

Теперь легко проверить, что каждая диагональ может содержать элементы в произвольном порядке - вам просто нужно сделать их достаточно большими. В частности, сортировка матрицы подразумевает сортировку каждой из этих диагоналей. iдиагональ i записи, и как таковые i!Возможен заказ. Таким образом, отсортированная матрица может определить, по крайней мере,X=i=1ni! разные заказы. Теперь легко убедиться, чтожурнал2Иксзнак равноΩ(N2журналN), подразумевая, что в модели сравнения (и, как Джефф указывает ниже, в любой бинарной модели дерева решений), по крайней мере, это нижняя граница времени сортировки.

Сариэль Хар-Пелед
источник
3
Опять же, в любой бинарной модели дерева решений, а не только в сравнении.
Джефф