Привет, Хабр! Давайте поговорим об алгоритмах.
Новички часто воспринимают их как что-то тяжелое, сложное и непонятное, и отчасти это так, но в основе лежат алгоритмы.
И чем лучше вы знаете основы своей специальности, тем больше у вас шансов добиться в ней успеха.
Сегодня мы рассмотрим одну красивую задачу по алгоритмам.
Давайте не будем отпугивать людей работа с алгоритмами в самом начале, поэтому в нашем анализе не будет ни раскидистых деревьев отрезков, ни неподходящих оптимизаций задачи о рюкзаке, ни вероятностных тестов на простоту.
Удобные алгоритмы.
Вот задача: найти максимальную разницу между соседями.
Дан массив из N целых чисел.
Он никак не упорядочен, и цифры могут повторяться.
Предположим, мы отсортировали его и вычислили разницу между каждой парой последовательных элементов.
Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.
Трудный? Вы можете попробовать это, прежде чем нажать «Подробнее», а затем мы проверим решение.
Итак, начнем.
Максимальная разница между соседями.
Давайте посмотрим на пример: Пусть дан массив из N=11 элементов.
Для начала давайте решим проблему наивно, это часто помогает. Мы можем сделать именно то, чего требует от нас задача — отсортировать числа и найти разницу между соседними элементами.
В зависимости от того, какую сортировку мы используем, сложность решения будет варьироваться.
Если мы используем qсортировка или Сортировка слиянием , то временная сложность будет 
.
Если мы знаем, что числа распределены довольно плотно по множеству целых чисел, мы можем использовать сортировку подсчетом.
Тогда мы получим 
, где U — разница между максимальным и минимальным элементом.
Случай относительно редкий, но стоит помнить о такой возможности.
После сортировки получаем массив: 
Выпишем массив отличий: 
Мы находим, что максимальная разница равна 6.
Теперь давайте подумаем, можно ли решить проблему быстрее? При переборе пар соседних элементов мы будем рассматривать множество пар с небольшой разницей.
Такие пары, возможно, никогда не смогут дать наибольшую разницу.
И действительно, в отсортированном массиве мы имеем 
пары соседних чисел, пусть разница между максимальным и минимальным равна 
.
Тогда наибольшая разница должна иметь значение не менее 
.
Эта оценка верна согласно принципу Дирихле.
Если голуби рассажены в клетках, и количество голубей превышает количество клеток, то хотя бы в одной из клеток содержится более одного голубя.
В 9 клетках содержится 10 голубей, согласно принципу Дирихле хотя бы в одной клетке содержится более одного голубя ( Википедия ) Позволять
, …
,
— i-й элемент отсортированного массива.
Затем 
.
Если предположить, что максимум всех D[i] меньше
, то вся сумма 
будет строго меньше U – противоречие.
Отлично, мы получили нижнюю оценку максимальной разницы! Теперь попробуем как-то локализовать слишком близкие друг к другу элементы — разделим отрезок от минимального до максимального элемента на полуинтервалы длины.
.
Каждый элемент попадет ровно в один полуинтервал.
Получаем разделение всех элементов на непересекающиеся группы, их еще называют пакетами.
Определить, в каком именно из них находится элемент x, очень просто — нужно посчитать 1 + int((x — a_min)/L) (нумеруем от единицы), где a_min — минимальный элемент в массиве A, его можно найти за один проход через исходный массив.
Единственным исключением является максимальный элемент – элементы с таким значением лучше изготавливать отдельной партией.
На рисунке показано распределение из примера, описанного выше.
Для наглядности проделаем эту процедуру вручную: 
Распределение по партиям осуществляется в линейном времени и требует 
дополнительная память.
Обратите внимание, что элементы из одной партии не могут давать максимальную разницу между двумя элементами.
Мы специально таким образом подбирали его размер.
Где могут располагаться два элемента, соседние по значению? Разумеется, в соседних непустых партиях! Например, на рисунке элементы из третьего и шестого пакета могут находиться в отсортированном массиве подряд, так как пакеты между ними пусты.
Понятно, что соседствовать будут только два элемента — максимальный из 3-й партии и минимальный из 6-й партии.
Аналогично, кандидатами в пару с максимальной разницей будут максимальный элемент первой партии и минимальный элемент третьей.
Запишем все возможные пары элементов, которые могут дать наибольшую разницу.
Обозначим min(i) минимальный элемент в i-й группе, а max(i) максимальный элемент. макс(1) = -1 мин(3) = 3 макс(3) = 4 мин(6) = 10 макс(6) = 10 мин(8) = 15 макс(8) = 15 мин(10) = 20 макс(10) = 21 мин(11) = 22 Мы определили пары, на которые стоит обратить внимание.
На практике приходится делать один проход по всем партиям, сохраняя последнюю непустую партию и максимальное значение в ней.
Когда нам попадётся очередная непустая партия, мы найдём в ней минимум и попытаемся обновить ответ.
Будем радоваться - мы вовремя решили проблему 
.
На самом деле мы использовали довольно известную идею и по сути сделали первые шаги карманной сортировки, в оригинале она называется сортировка ведром .
ЭТовары помещаются в корзины, а затем элементы в каждой корзине сортируются.
В худшем случае она работает на 
, но среднее время работы при достаточном количестве партий и равномерном распределении элементов равно
.
«Но подождите, а как насчет случая, когда 
, почему ты не изучил это? - спросит внимательный читатель.
Этот случай вырожденный, поэтому мы его не рассматривали, но сделаем это сейчас для полноты вариантов.
Если разница между минимумом и максимумом равна нулю, то и максимальная разница также равна нулю.
Собственно, это все.
В опросе могут участвовать только зарегистрированные пользователи.
Войти , Пожалуйста.
Быстро ли вы решили? 14,46% Конечно, это начальный уровень 12 2,41% Прошло около 10 минут 2 6,02% Я решил, но по-своему (напишу в комментариях) 5 1,2% Можно было бы еще проще, покажу ты сейчас 1 65.06% Я даже не пробовал, сразу пошел смотреть твое решение 54 10.84 % Мне не нравятся алгоритмы 9 Проголосовали 83 пользователя.
27 пользователей воздержались.
Теги: #Алгоритмы #Учебный процесс в IT #Развлекательные задачи #мастерская #Яндекс.
Мастерская #курс по алгоритмам #массивы #сортировка #решение задач #сортировка слиянием #qsort #принцип Дирихле
-
Сбор Данных
19 Oct, 24 -
Экономика
19 Oct, 24 -
Проектирование И Именование Очередей
19 Oct, 24
