А сложность линейной не будет
Откуда такая уверенность?
Ну потому что мы получаем данные за линейную сложность, а потом работает с полученными данными много времени
Что мешает "много времени" так же быть линейным? Я пока до конца не додумал, но явных ограничений, почему нельзя за линейное время — не вижу.
Ну если сталин сорт и подобное не брать
Не только. Теоретический предел в nlogn — у сортировок сравнениями. То есть когда единственная доступная нам информация для принятия решения — результат сравнения двух элементов массива. Всякие bucket sort и подобные имеют другую асимптотику при определённых ограничениях на входные данные. А у нас данные сильно ограничены.
Соглашусь, я перечитал условие и понял, что тут на это и делался жирный намек, а я даже чет и не заметил
Блин, реально, тут же конкретно прям блочная сортировка идеально встает
Обсуждают сегодня