Я смущен. Я хочу доказать, что это проблема сортировки по матрица, т.е. строки и столбцы в порядке возрастания , Я исхожу из предположения, что это можно сделать быстрее, чем и попытаться нарушить нижняя граница для сравнений, необходимых для сортировки m элементов. У меня есть два противоречивых ответа:
- мы можем получить отсортированный список элементы из отсортированной матрицы в /math/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
- Вы не можете получить отсортированный список из матрицы быстрее, чем /programming/4279524/how-to-sort-amxn-matrix-which-has- все его-м-строки отсортированные-и-н-колонки-отсортировано
Какой из них прав?
time-complexity
lower-bounds
matrices
sorting
asymptotics
user2038833
источник
источник
Ответы:
Нижняя граница верна (2) - вы не можете сделать это лучше, чемΩ(n2logn) и (1), конечно, неправильно. Давайте сначала определим, что такое отсортированная матрица - это матрица, в которой элементы в каждой строке и столбце сортируются в порядке возрастания.
Теперь легко проверить, что каждая диагональ может содержать элементы в произвольном порядке - вам просто нужно сделать их достаточно большими. В частности, сортировка матрицы подразумевает сортировку каждой из этих диагоналей.i диагональ i записи, и как таковые i! Возможен заказ. Таким образом, отсортированная матрица может определить, по крайней мере,Иксзнак равноΠNя = 1я ! разные заказы. Теперь легко убедиться, чтожурнал2Икс= Ω (N2журналн ) , подразумевая, что в модели сравнения (и, как Джефф указывает ниже, в любой бинарной модели дерева решений), по крайней мере, это нижняя граница времени сортировки.
источник