Комментарии 24
"В худшем случае она работает за O(n^2), но среднее время работы при достаточном количестве батчей и равномерном распределении элементов составляет O(n)."
А сколько их, таких худших случаев?
Если мало, то для них наверно есть свой алгоритм?
Допустим, есть 100 элементов. Самый маленький равен 1, самый большой 10'000, а все остальные как-то расположены на отрезке от 5001 до 5100. Тогда все элементы, кроме двух крайний попадут в один батч. Иными словами, есть батч, в котором находится O(n) элементов. В этом случае общее время исполнения будет зависеть от того, какая сортировка используется уже внутри батчей. Если это квадратичная сортировка, то итоговая сложность O(n^2), когда в одном батче оказывается O(n) элементов. Если же использовать что-то побыстрее (например, сортировку слиянием), то получим O(n log n). Мы могли бы в таком случае сразу использовать более стандартную сортировку (можно опять сортировку слиянием взять) и получить те же O(n log n).
то есть в общем случае — нет никакого смыла использовать этот алгоритм. Всё равно получается O(n log n)
Так и у вашего алгоритма сложность не O(N), а O(U/N + N), потому что:
А U/N может быть гораздо больше чем N, как в вашем же примере из этого комментария.
На практике необходимо сделать один проход по всем батчам
А U/N может быть гораздо больше чем N, как в вашем же примере из этого комментария.
Ну если сортировать 32-битные или 64-битные инты или даже флоты, то всегда будет O(n), просто с большой константой спереди, возможно, даже большей, чем log n.
Вот задача: найти максимальную разницу между соседями.
Мы можем сделать именно то, что от нас требует условие задачи — отсортировать числа и найти разницу между соседними элементами
Простите, но где в условии вы увидели хоть что-то про сортировку? А так-как дальше много рассуждений о разных сортировках, то было-бы неплохо написать корректное условие, так как сортировка сильно меняет соседние элементы, следовательно и максимальная разница после сортировки может быть другой. А если условие верное, то к чему тогда вообще рассуждения о сортировке, которой в принципе не должно быть в решении?
Полностью согласен, без сортировки этой задаче даже новичку надо постараться дать алгоритм сложнее линейного.
Это условное название задачи, а не точная формулировка. Сама формулировка приведена сразу ниже
Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.
И где в формулировке сказано, что массив надо сортировать?
"Предположим, что мы отсортировали его" — это по-вашему формулировка того, что массив надо сортировать?
Тут-же написано что массив уже отсортировали (если вы считаете это формулировкой все еще), но вы сразу-же пишите «В зависимости от того, какую сортировку мы будем использовать»… Т.е. мы еще не отсортировали его? так определитесь:
1 — предположим что уже отсортировали
или
2 — предположим что надо сортировать.
Либо в условии не сказано что надо сортировать, либо сказано что мы уже отсортировали, но я никак не соглашусь, что в условии сказано о необходимости сортировать массив.
А то для меня по работе весьма знакома задача — найти максимальную разницу между соседями. И это у меня на работе по несколько раз в день выполняется, и при этом ни разу не требовалось данные сортировать, так-как порядок их получения всегда имеет значение, только поэтому заголовок меня и заинтересовал, думал тут будет что-то интересное в знакомой задаче.
"Предположим, что мы отсортировали его" — это по-вашему формулировка того, что массив надо сортировать?
Тут-же написано что массив уже отсортировали (если вы считаете это формулировкой все еще), но вы сразу-же пишите «В зависимости от того, какую сортировку мы будем использовать»… Т.е. мы еще не отсортировали его? так определитесь:
1 — предположим что уже отсортировали
или
2 — предположим что надо сортировать.
Либо в условии не сказано что надо сортировать, либо сказано что мы уже отсортировали, но я никак не соглашусь, что в условии сказано о необходимости сортировать массив.
А то для меня по работе весьма знакома задача — найти максимальную разницу между соседями. И это у меня на работе по несколько раз в день выполняется, и при этом ни разу не требовалось данные сортировать, так-как порядок их получения всегда имеет значение, только поэтому заголовок меня и заинтересовал, думал тут будет что-то интересное в знакомой задаче.
Данные, с которыми мы работаем, не отсортированы.
В этом предложении мы вводим интересующий нас объект. У этого объекта есть какое-то свойство — максимальная разница между соседними элементами. И найти её мы стремимся без использования сортировок (что и происходит далее), то есть без построения самого объекта.
Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов.
В этом предложении мы вводим интересующий нас объект. У этого объекта есть какое-то свойство — максимальная разница между соседними элементами. И найти её мы стремимся без использования сортировок (что и происходит далее), то есть без построения самого объекта.
Я бы первой строчкой, используя библиотечную функцию, отсортировал массив, а второй строчкой по нему пробежался. Всё.
А изобретать что-то специальное имеет смысл только в том случае, когда это действительно оправдано.
Распределение по батчам выполняется за линейное время и требует O(n) дополнительной памяти.
Кажется, что для решения исходной задачи необязательно раскидывать элементы по батчам и достаточно у каждого подсчитывать минимум и максимум. Таким образом, можно добиться O(кол-во непустых батчей), ну и заодно сократить количество проходов по массиву.
Где могут находиться два соседних по значениям элемента? Конечно же, в соседних непустых батчах!
Но они ведь могут и в одном батче находиться — особенно, если все батчи непустые. Или я что-то упускаю?
Насчет О(N) алгоритма для целых чисел — radix sort + один проход для нахождения максимальной разности. На плавающие тоже можно обобщить.
Спасибо, что обратили внимание на крайний случай! Если все батчи заполненные, то в каждом будет по одному элементу, так как батчей всего N (последний элемент в отдельном батче и N-1 нормальных). Это в некотором смысле вырожденный случай, внутри одного батча не может образоваться пара — элементов не хватает.
Исключение составит только максимальный элемент — элементы с таким значением лучше сделать отдельным батчом.
Думаю, здесь нужно написать батчем.
«Но постойте, а как же случай, когда U=0, почему вы не рассмотрели его?», — спросит внимательный читатель.
Лишняя запятая после кавычек. Пруф: http://gramota.ru/class/coach/punct/45_192.
Вот задача: найти максимальную разницу между соседями.
Что-то я туплю. Зачем сортировать массив чтоб найти наибольшую разницу между соседями?
Просто пройтись по массиву, на каждой итерации смотреть разницу между соседями, и в итоге сохранить наибольшую — этого разве недостаточно?
Выше есть комментарий про это — habr.com/ru/company/yandex_praktikum/blog/531748/?reply_to=22414706#comment_22399382
В формулировке говорится про максимальную разницу между элементами упорядоченного массива, а изначально элементы стоят в произвольном порядке.
В формулировке говорится про максимальную разницу между элементами упорядоченного массива, а изначально элементы стоят в произвольном порядке.
Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу
Хмм, всё-равно не совсем понятно. Т.е. массив УЖЕ отсортировали, и УЖЕ вычислили все «разницы» между соседними элементами?
Получается нужно найти максимальное число из множества?
В опросе не хватает пункта "Не люблю формулы", выбрал бы его.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ищем максимальную разницу между соседями. User-friendly-разбор задачи по алгоритмам