Разделяй и властвуй алгоритм | Вступление

Как и « Жадное» и « Динамическое программирование» , «Разделяй и властвуй» — это алгоритмическая парадигма. Типичный алгоритм «Разделяй и властвуй» решает проблему, используя следующие три шага.

1. Разделить: разбить данную проблему на подзадачи того же типа.
2. Завоевать: рекурсивно решить эти подзадачи
3. Объединить: надлежащим образом объединить ответы

Ниже приведены некоторые стандартные алгоритмы, которые являются алгоритмами «разделяй и властвуй».

1) Бинарный поиск — это алгоритм поиска. На каждом шаге алгоритм сравнивает входной элемент x со значением среднего элемента в массиве. Если значения совпадают, вернуть индекс среднего. В противном случае, если x меньше среднего элемента, алгоритм повторяется для левой части среднего элемента, в противном случае — для правой части среднего элемента.

2) Быстрая сортировка — это алгоритм сортировки. Алгоритм выбирает элемент поворота, переставляет элементы массива таким образом, что все элементы, меньшие, чем выбранный элемент поворота, перемещаются в левую сторону поворота, а все более крупные элементы перемещаются в правую сторону. Наконец, алгоритм рекурсивно сортирует подмассивы слева и справа от элемента pivot.

3) Merge Sort — также алгоритм сортировки. Алгоритм делит массив на две половины, рекурсивно сортирует их и, наконец, объединяет две отсортированные половины.

4) Ближайшая пара точек Задача состоит в том, чтобы найти ближайшую пару точек в наборе точек в плоскости xy. Задача может быть решена за время O (n ^ 2) путем вычисления расстояний каждой пары точек и сравнения расстояний для нахождения минимума. Алгоритм «Разделяй и властвуй» решает задачу за O (nLogn) время.

5) Алгоритм Штрассена — эффективный алгоритм умножения двух матриц. Простой метод умножения двух матриц требует 3 вложенных цикла и является O (n ^ 3). Алгоритм Штрассена умножает две матрицы за O (n ^ 2.8974) времени.

6) Алгоритм быстрого преобразования Фурье (БПФ ) Кули – Тьюки является наиболее распространенным алгоритмом для БПФ. Это алгоритм «разделяй и властвуй», который работает за O (nlogn) время.

7) Алгоритм Карацубы для быстрого умножения выполняет умножение не более двух n- значных чисел однозначные умножения в целом (и точно когда n является степенью 2). Поэтому он работает быстрее, чем классический алгоритм, который требует n ² однозначных произведений. В частности, если n = 2 ¹⁰ = 1024, точные значения составляют 3 ¹⁰ = 59 049 и (2 ¹⁰ ) ² = 1 048 576 соответственно.

Мы будем публиковать вышеприведенные алгоритмы в отдельных постах.

Разделяй и властвуй (D & C) против динамического программирования (DP)
Обе парадигмы (D & C и DP) разделяют данную проблему на подзадачи и решают подзадачи. Как выбрать один из них для данной проблемы? Разделяй и властвуй следует использовать, когда одни и те же подзадачи не оцениваются много раз. В противном случае следует использовать динамическое программирование или запоминание. Например, бинарный поиск — это алгоритм «разделяй и властвуй», мы никогда не оцениваем одни и те же подзадачи. С другой стороны, для вычисления n-го числа Фибоначчи, динамическое программирование должно быть предпочтительным (см. Это для деталей).

Ссылки
Алгоритмы Санджоя Дасгупты, Христоса Пападимитриу, Умеша Вазирани
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.
http://en.wikipedia.org/wiki/Karatsuba_algorithm

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

• Алгоритм Карацубы для быстрого умножения с использованием алгоритма «Разделяй и властвуй»
• Ближайшая пара точек с использованием алгоритма «разделяй и властвуй»
• Максимальная сумма подмассива с использованием алгоритма «разделяй и властвуй»
• Разделяй и властвуй | Набор 5 (матричное умножение Штрассена)
• Поиск в отсортированном по строке и по столбцам двумерном массиве с использованием алгоритма «разделяй и властвуй»
• Проблема листов с использованием алгоритма «разделяй и властвуй»
• Проблема горизонта с использованием алгоритма «разделяй и властвуй»
• Самый длинный общий префикс с использованием алгоритма «разделяй и властвуй»
• Быстрый алгоритм для выпуклого корпуса
• Выпуклая оболочка с использованием алгоритма «разделяй и властвуй»
• Рандомизированный алгоритм двоичного поиска
• Продвинутая основная теорема для рецидивов «разделяй и властвуй»
• Уменьшить и победить
• Отдельные элементы в подмассиве с использованием алгоритма Мо
• Динамическое программирование против разделяй и властвуй