РАЗДЕЛЯЙ И ВЛАСТВУЙ
Рекурсивная стратегия решения задач, которая заключается в приведении задачи
(упрощении, делении, уменьшении) к простейшему базовому случаю.
- Сначала нужно найти этот базовый случай
- Затем найти способ упростить исходную задачу до него
АЛГОИТМ ЕВКЛИДА
Примером применения стратегии "Разделяй и властвуй" является нахождение
наибольшего общего делителя двух чисел с помощью алгоритма Евклида
При этом числа постенно уменьшаются, пока не достигнут собственно
значения наибольшего общего делителя.
Пример
У фермера есть большой прямоугольный участок земли. Он хочет разделить
его на равные квадратные участки максимального размера.
По сути эта задача сводится к нахождению НОД для длины и ширины исходного участка.
Пример Nod в этой главе
РАБОТА С МАССИВАМИ
Пример суммы в массиве с использованием рекурсии - Sum
БЫСТРАЯ СОРТИРОВКА
Алгоритм сортировки, основанный на принципе "Разделяй и властвуй".
Базовый случай - это массив с одним элементом, который сам по себе уже является
отсортированным. Базовым случаем также является пустой массив.
В исходном массиве выбирается опорный элемент. Затем массив делится на три части:
- элементы, которые меньше опорного
- опорный элемент
- элементы, которые больше опорного
Теперь задача сводится к двум меньшим задачам: отсортировать два подмассива.
Рекурсивное разделение происходит до тех пор, пока не будет достигнут базовый случай.
Примеры сортировок Quick1 и Quick2 в данном разделе
ЭФФЕКТИВНОСТЬ АЛГОРИТМА
Эффективность алгоритма во многом зависит от выбора опорного элемента.
В худшем случае: O(n2)
Массив уже отсортирован, в качестве опорного берется первый элемент.
В среднем случае: O(n * log n)
Массив уже отсортирован, в качестве опорного берется средний элемент.
На каждом витке алгоритм обращается ко всем элементам массива, независимо от того,
как они отсортированы. Поэтому эффективность зависит от высоты стека. В худшем случае
высота стека будет равна n. В лучшем случае высота стека log n, так как каждый раз
массив делится на две равные части.
Сортировка слиянием (еще один алгоритм сортировки) имеет эффективность O(n * log n)
в худшем случае. Можно было бы предположить, что выгоднее всегда использовать сортировку
слиянием, а не быструю сортировку.
Однако при одинаковом времени O-большое эти алгоритмы имеют разное реальное время выполнения.
В O-большом игнорируется константа (время выполнения одной операции), но у быстрой сортировки
она меньше, чем у сортировки слиянием.