Рекурсивный поиск и сортировка
| English | Русский |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | разделяй и властвуй |
| merge sort/mɜːdʒ sɔːt/ | сортировка слиянием |
| merge/mɜːdʒ/ | сливаться |
Рекурсия в поиске и сортировке
- Та же идея разделяй и властвуй лежит в основе рекурсивного бинарного поиска и сортировки слиянием.
- Разделите задачу пополам, решите половины, объедините.
- Рекурсивный бинарный поиск ищет в одной половине, вызывая сам себя для неё.
- Сортировка слиянием сортирует каждую половину, затем сливает отсортированные половины вместе.
Рекурсивный бинарный поиск
- Базовый случай: пустой диапазон означает, что целевой элемент не найден.
- Посмотрите на средний элемент. Если это цель, верните его индекс.
- Если цель меньше, рекурсируйте по левой половине; если больше, то по правой.
- Каждый вызов делит диапазон пополам — та же сложность
O(log n), записанная рекурсивно.
Сортировка слиянием
- Разделите массив на две половины; отсортируйте каждую половину рекурсивно.
- Базовый случай: массив из 0 или 1 элемента уже отсортирован.
- Слияние: пройдите обе отсортированные половины, всегда беря меньший элемент спереди.
- Гораздо быстрее, чем
n²сортировки — околоn log nработы.
Почему побеждает «разделяй и властвуй»
- Деление задачи пополам на каждом шаге дает коэффициент
log n. - Сортировка слиянием
n log nпревосходит сортировку выбором/вставкойn²на больших массивах. - Базовый случай (пустой или один элемент) останавливает каждую ветвь.
- Та же форма, что и у любой рекурсии: разделение вниз, объединение вверх.
Рекурсивный бинарный поиск рекурсирует только по ОДНОЙ половине (цель находится только с одной стороны); сортировка слиянием рекурсирует по ОБЕИМ половинам, а затем сливает их. Обе требуют базового случая — пустой диапазон означает «не найдено» для поиска; массив из 0 или 1 элемента уже отсортирован для сортировки слиянием. Именно «разделяй и властвуй» делает их быстрыми (O(log n) и O(n log n)).
Сортировка слиянием на [3, 1, 2, 4]:
- Разделите на
[3, 1]и[2, 4]; отсортируйте каждую →[1, 3]и[2, 4]. - Слияние: возьмите 1, затем 2, затем 3, затем 4 →
[1, 2, 3, 4]. - При каждом слиянии по очереди выбирается меньший элемент из начала каждого списка.
Рекурсивный двоичный поиск рекурсирует по одной половине (базовый случай: пустой диапазон = не найдено) для O(log n) поиска. Сортировка слиянием рекурсирует по обеим половинам и сливает их (базовый случай: 0 или 1 элемент) для O(n log n) сортировки. Оба подхода используют метод «разделяй и властвуй»: разбивают задачу вниз и объединяют результаты вверх — это значительно быстрее, чем n².
Merge sort делит пополам, затем объединяет снизу вверх
Одиночные элементы уже отсортированы (базовый случай); merge объединяет их снизу вверх.
Рекурсивный бинарный поиск рекурсивно применяется к...
Цель находится только с одной стороны от середины.
Merge sort рекурсивно применяется к...
Отсортировать каждую половину, затем объединить две отсортированные половины.
Базовый случай для merge sort — массив из...
Один (или ноль) элемент не требует сортировки.
Время выполнения merge sort составляет около...
log n уровней деления, работа n на уровне.
И рекурсивный бинарный поиск, и merge sort являются алгоритмами «разделяй и властвуй».
Оба делят задачу пополам и рекурсивно применяют её.
Расставьте шаги объединения для половин [1,3] и [2,4].
Всегда берите меньший элемент спереди: 1, 2, 3, 4.