[Занимательные задачки, Алгоритмы, Учебный процесс в IT] Ищем максимальную разницу между соседями. User-friendly-разбор задачи по алгоритмам
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Привет, Хабр!
Давайте поговорим про алгоритмы. Новички часто воспринимают их как что-то тяжёлое, сложное и непонятное, и отчасти это правда, но алгоритмы — это базис. А чем лучше вы знаете базис своей специальности, тем с большей вероятностью преуспеете в ней.
Сегодня мы посмотрим на одну красивую задачу по алгоритмам. Не будем отпугивать людей от работы с алгоритмами на самом старте, поэтому в нашем разборе не будет ни развесистых деревьев отрезков, ни разномастных оптимизаций задачи о рюкзаке, ни вероятностных тестов на простоту. User-friendly algos.
Вот задача: найти максимальную разницу между соседями.
Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.
Сложно? Можете попробовать сделать это до того, как нажмёте «Читать дальше», а потом проверим решение.
Итак, поехали. Максимальная разница между соседями.
Рассмотрим пример:
Пусть дан массив из N=11 элементов.
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]
Cначала решим задачу наивно, это часто помогает. Мы можем сделать именно то, что от нас требует условие задачи — отсортировать числа и найти разницу между соседними элементами. В зависимости от того, какую сортировку мы будем использовать, сложность решения будет варьироваться.
Если используем qsort или mergesort, то временная сложность составит O(N log N). Если нам известно, что числа распределены достаточно плотно на множестве целых чисел, то можно использовать сортировку подсчётом. Тогда мы получим O(U + N), где U — разность между максимальным и минимальным элементом. Случай относительно редкий, но стоит помнить про такую возможность.
После сортировки получим массив:
As = [-3, -2, -1, 3, 4, 10, 10, 15, 20, 21, 22]
Выпишем массив разностей: D = [1, 1, 4, 1, 6, 0, 5, 5, 1, 1]
Получаем, что максимальная разница составляет 6.
Теперь подумаем, можно ли решить задачу быстрее? При переборе пар соседних элементов мы будем рассматривать много пар с маленькой разностью. Такие пары, возможно, и не смогут никогда дать наибольшую разность. И действительно, в отсортированном массиве у нас есть N-1 пара соседних чисел, разность между максимумом и минимумом пусть равна U. Тогда у наибольшей разности значение должно быть хотя бы U / (N — 1). Эта оценка верна по принципу Дирихле.
Если голуби рассажены в клетки, причём число голубей больше числа клеток, то хотя бы в одной из клеток находится более одного голубя.
9 клеток содержат 10 голубей, по принципу Дирихле, хотя бы в одной клетке находятся более одного голубя (Википедия)
Пусть D[1] = As[2] — As[1], … D[n — 1] = As[n] — As[n — 1], As — i-й элемент отсортированного массива. Тогда D >= 0, D[1] + … + D[N-1] = U.
Если предположить, что максимум из всех D меньше U/(N-1), то вся сумма D[1] + … + D[N-1] будет строго меньше U — противоречие.
Отлично, мы получили нижнюю оценку на максимальную разность! Теперь попробуем как-то локализовать слишком близкие друг к другу элементы — разобьём отрезок от минимального до максимального элемента на полуинтервалы длиной L=U/(N-1). Каждый элемент попадёт ровно в один полуинтервал. Получим разбиение всех элементов на непересекающиеся группы, их ещё называют батчами.
Определить, в какой именно из них попал элемент x, очень просто — надо вычислить 1 + int((x — a_min) / L) (нумеруем с единицы), где a_min — минимальный элемент в массиве A, его можно найти за один проход по исходному массиву. Исключение составит только максимальный элемент — элементы с таким значением лучше сделать отдельным батчом.
На рисунке представлено распределение из описанного выше примера. Для ясности проделаем эту процедуру руками:
U = 22 — (-3) = 25, N = 11 => L = 25/(11-1) = 2.5
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]
(-1 — (-3)) / 2.5 = 0.8 => batch = 1
(-3 — (-3)) / 2.5 = 0 => batch = 1
(10 — (-3)) / 2.5 = 13/2.5 = 5.2 =>batch = 6
(20 — (-3)) / 2.5 = 23/2.5 = 9.2 => batch = 10
(21 — (-3)) / 2.5 = 24/2.5 = 9.6 => batch = 10
(4 — (-3)) / 2.5 = 7/2.5 = 2.8 => batch = 3
(3 — (-3)) / 2.5 = 6/2.5 = 2.4 => batch = 3
(22 — (-3)) / 2.5 = 10 => batch = 11
(10 — (-3)) / 2.5 = 5.2 => batch = 6
(-2 — (-3)) / 2.5 = 0.4 => batch = 1
(15 — (-3)) / 2.5 = 7.2 => batch = 8
Распределение по батчам выполняется за линейное время и требует O(n) дополнительной памяти. Обратите внимание, что элементы из одного батча не могут дать максимальную разницу между двумя элементами. Мы специально подобрали его размер таким образом.
Где могут находиться два соседних по значениям элемента? Конечно же, в соседних непустых батчах! Например, на рисунке элементы из третьего и шестого батча могут идти подряд в отсортированном массиве, так как батчи между ними пустые. Понятно, что соседними будут только два элемента — максимум из 3-го батча и минимум из 6-го. Аналогично, кандидатами на пару с максимальной разностью будут максимальный элемент первого батча и минимальный элемент третьего.
Выпишем все возможные пары элементов, которые могут дать наибольшую разность. Обозначим как min(i) — минимальный элемент в i-й группе, как max(i) — максимальный элемент.
max(1) = -1 min(3) = 3
max(3) = 4 min(6) = 10
max(6) = 10 min(8) = 15
max(8) = 15 min(10) = 20
max(10) = 21 min(11) = 22
Мы определили пары, которые стоит рассматривать. На практике необходимо сделать один проход по всем батчам, поддерживать последний непустой батч и максимальное значение в нём. Когда мы наткнёмся на следующий непустой батч, то найдём в нём минимум и попробуем обновить ответ.
Порадуемся — мы решили задачу за время O(N).
На самом деле, мы использовали достаточно известную идею и по сути проделали первые шаги карманной сортировки, в оригинале её называют bucket-sort.
Элементы раскладываются по корзинам, а потом элементы в каждой корзине сортируются
В худшем случае она работает за O(n^2), но среднее время работы при достаточном количестве батчей и равномерном распределении элементов составляет O(n).
«Но постойте, а как же случай, когда U=0, почему вы не рассмотрели его?», — спросит внимательный читатель. Этот случай вырожденный, вот мы его и не рассмотрели, но давайте сделаем это сейчас для полноты вариантов.
Если разница между минимумом и максимумом равно нулю, то максимальная разница тоже равна нулю. Собственно, это всё.
===========
Источник:
habr.com
===========
Похожие новости:
- [Алгоритмы, Хакатоны] Участники хакатона разработали алгоритм для поиска информации в газетах военных лет
- [Криптография, Алгоритмы] Генераторы псевдослучайных чисел на основе РСЛОС
- [Машинное обучение, Учебный процесс в IT, Карьера в IT-индустрии, Искусственный интеллект] Наука это интересно. Science Club от MIL Team — новый формат работы над научными задачами
- [Учебный процесс в IT, Лайфхаки для гиков, Мозг] Замедлиться, чтобы быстрее учиться новому — подробно обсуждаем ключевые рекомендации
- [Учебный процесс в IT, Лайфхаки для гиков, Мозг] Замедлиться, чтобы быстрее учиться новому — подробно обсуждаем ключевые рекомендации
- [Учебный процесс в IT, Образование за рубежом, Биотехнологии, Химия] Какие образовательные возможности предлагает новый центр Инфохимии в Университете ИТМО
- [Анализ и проектирование систем, Алгоритмы, Видеотехника, Физика] Синтез суперсверхширокоугольного объектива (насадки) для инфракрасной области спектра
- [Программирование, Алгоритмы, Go] Algorithms in Go: Sliding Window Pattern
- [Ненормальное программирование, Занимательные задачки, Программирование, Искусственный интеллект] Russian AI Cup 2020 — a new strategy game for developers
- [Беспроводные технологии, Разработка систем связи, Искусственный интеллект, Транспорт] Самообучающийся ИИ начал управлять навигацией раздающих интернет аэростатов Loon
Теги для поиска: #_zanimatelnye_zadachki (Занимательные задачки), #_algoritmy (Алгоритмы), #_uchebnyj_protsess_v_it (Учебный процесс в IT), #_problem_solving, #_algoritmy (алгоритмы), #_jandeks_praktikum (Яндекс Практикум), #_printsip_dirihle (принцип Дирихле), #_sortirovka (сортировка), #_massivy (массивы), #_qsort, #_mergesort, #_blog_kompanii_jandeks.praktikum (
Блог компании Яндекс.Практикум
), #_zanimatelnye_zadachki (
Занимательные задачки
), #_algoritmy (
Алгоритмы
), #_uchebnyj_protsess_v_it (
Учебный процесс в IT
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 11:15
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Привет, Хабр! Давайте поговорим про алгоритмы. Новички часто воспринимают их как что-то тяжёлое, сложное и непонятное, и отчасти это правда, но алгоритмы — это базис. А чем лучше вы знаете базис своей специальности, тем с большей вероятностью преуспеете в ней.  Сегодня мы посмотрим на одну красивую задачу по алгоритмам. Не будем отпугивать людей от работы с алгоритмами на самом старте, поэтому в нашем разборе не будет ни развесистых деревьев отрезков, ни разномастных оптимизаций задачи о рюкзаке, ни вероятностных тестов на простоту. User-friendly algos. Вот задача: найти максимальную разницу между соседями. Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом. Сложно? Можете попробовать сделать это до того, как нажмёте «Читать дальше», а потом проверим решение. Итак, поехали. Максимальная разница между соседями. Рассмотрим пример: Пусть дан массив из N=11 элементов. A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15] Cначала решим задачу наивно, это часто помогает. Мы можем сделать именно то, что от нас требует условие задачи — отсортировать числа и найти разницу между соседними элементами. В зависимости от того, какую сортировку мы будем использовать, сложность решения будет варьироваться. Если используем qsort или mergesort, то временная сложность составит O(N log N). Если нам известно, что числа распределены достаточно плотно на множестве целых чисел, то можно использовать сортировку подсчётом. Тогда мы получим O(U + N), где U — разность между максимальным и минимальным элементом. Случай относительно редкий, но стоит помнить про такую возможность. После сортировки получим массив: As = [-3, -2, -1, 3, 4, 10, 10, 15, 20, 21, 22] Выпишем массив разностей: D = [1, 1, 4, 1, 6, 0, 5, 5, 1, 1] Получаем, что максимальная разница составляет 6. Теперь подумаем, можно ли решить задачу быстрее? При переборе пар соседних элементов мы будем рассматривать много пар с маленькой разностью. Такие пары, возможно, и не смогут никогда дать наибольшую разность. И действительно, в отсортированном массиве у нас есть N-1 пара соседних чисел, разность между максимумом и минимумом пусть равна U. Тогда у наибольшей разности значение должно быть хотя бы U / (N — 1). Эта оценка верна по принципу Дирихле. Если голуби рассажены в клетки, причём число голубей больше числа клеток, то хотя бы в одной из клеток находится более одного голубя.
 9 клеток содержат 10 голубей, по принципу Дирихле, хотя бы в одной клетке находятся более одного голубя (Википедия) Пусть D[1] = As[2] — As[1], … D[n — 1] = As[n] — As[n — 1], As — i-й элемент отсортированного массива. Тогда D >= 0, D[1] + … + D[N-1] = U. Если предположить, что максимум из всех D меньше U/(N-1), то вся сумма D[1] + … + D[N-1] будет строго меньше U — противоречие. Отлично, мы получили нижнюю оценку на максимальную разность! Теперь попробуем как-то локализовать слишком близкие друг к другу элементы — разобьём отрезок от минимального до максимального элемента на полуинтервалы длиной L=U/(N-1). Каждый элемент попадёт ровно в один полуинтервал. Получим разбиение всех элементов на непересекающиеся группы, их ещё называют батчами. Определить, в какой именно из них попал элемент x, очень просто — надо вычислить 1 + int((x — a_min) / L) (нумеруем с единицы), где a_min — минимальный элемент в массиве A, его можно найти за один проход по исходному массиву. Исключение составит только максимальный элемент — элементы с таким значением лучше сделать отдельным батчом. На рисунке представлено распределение из описанного выше примера. Для ясности проделаем эту процедуру руками: U = 22 — (-3) = 25, N = 11 => L = 25/(11-1) = 2.5 A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15] (-1 — (-3)) / 2.5 = 0.8 => batch = 1 (-3 — (-3)) / 2.5 = 0 => batch = 1 (10 — (-3)) / 2.5 = 13/2.5 = 5.2 =>batch = 6 (20 — (-3)) / 2.5 = 23/2.5 = 9.2 => batch = 10 (21 — (-3)) / 2.5 = 24/2.5 = 9.6 => batch = 10 (4 — (-3)) / 2.5 = 7/2.5 = 2.8 => batch = 3 (3 — (-3)) / 2.5 = 6/2.5 = 2.4 => batch = 3 (22 — (-3)) / 2.5 = 10 => batch = 11 (10 — (-3)) / 2.5 = 5.2 => batch = 6 (-2 — (-3)) / 2.5 = 0.4 => batch = 1 (15 — (-3)) / 2.5 = 7.2 => batch = 8  Распределение по батчам выполняется за линейное время и требует O(n) дополнительной памяти. Обратите внимание, что элементы из одного батча не могут дать максимальную разницу между двумя элементами. Мы специально подобрали его размер таким образом. Где могут находиться два соседних по значениям элемента? Конечно же, в соседних непустых батчах! Например, на рисунке элементы из третьего и шестого батча могут идти подряд в отсортированном массиве, так как батчи между ними пустые. Понятно, что соседними будут только два элемента — максимум из 3-го батча и минимум из 6-го. Аналогично, кандидатами на пару с максимальной разностью будут максимальный элемент первого батча и минимальный элемент третьего. Выпишем все возможные пары элементов, которые могут дать наибольшую разность. Обозначим как min(i) — минимальный элемент в i-й группе, как max(i) — максимальный элемент. max(1) = -1 min(3) = 3 max(3) = 4 min(6) = 10 max(6) = 10 min(8) = 15 max(8) = 15 min(10) = 20 max(10) = 21 min(11) = 22 Мы определили пары, которые стоит рассматривать. На практике необходимо сделать один проход по всем батчам, поддерживать последний непустой батч и максимальное значение в нём. Когда мы наткнёмся на следующий непустой батч, то найдём в нём минимум и попробуем обновить ответ. Порадуемся — мы решили задачу за время O(N). На самом деле, мы использовали достаточно известную идею и по сути проделали первые шаги карманной сортировки, в оригинале её называют bucket-sort.  Элементы раскладываются по корзинам, а потом элементы в каждой корзине сортируются В худшем случае она работает за O(n^2), но среднее время работы при достаточном количестве батчей и равномерном распределении элементов составляет O(n). «Но постойте, а как же случай, когда U=0, почему вы не рассмотрели его?», — спросит внимательный читатель. Этот случай вырожденный, вот мы его и не рассмотрели, но давайте сделаем это сейчас для полноты вариантов. Если разница между минимумом и максимумом равно нулю, то максимальная разница тоже равна нулю. Собственно, это всё. =========== Источник: habr.com =========== Похожие новости:
Блог компании Яндекс.Практикум ), #_zanimatelnye_zadachki ( Занимательные задачки ), #_algoritmy ( Алгоритмы ), #_uchebnyj_protsess_v_it ( Учебный процесс в IT ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 11:15
Часовой пояс: UTC + 5