В соавторстве — Вишвеш Мехер, Сиддхи_Мундада, Дааниш Шейх, Теджас Муркья и СИДДХАРТ НАХАР

Если вы знакомы с британско-индийской историей, вы знаете, что означает «разделяй и властвуй», и с этой точки зрения это звучит не так уж хорошо. Но не бойтесь, это не урок истории :)

Введение

В этом блоге вы узнаете, как решать задачи программирования с помощью алгоритмических концепций Разделяй и властвуй и Жадность,а также некоторые различия между ними. Мы также рассмотрим некоторые термины и различные алгоритмы, которые классифицируются в соответствии с этими подходами.

Проблемы существуют во всех формах и проявлениях. Большие проблемы особенно сложно решить, если вы не знаете, как разбить их на небольшие подмножества и решить их по отдельности, а затем найти оптимальное решение. Нахождение решения основной проблемы путем решения набора подзадач является основной целью разделяй и властвуй, а также жадного подхода. То, как решаются эти подзадачи, является разницей между этими двумя подходами. Мы предполагаем, что читатель имеет базовые знания о том, что такое программирование, какова его логика и базовый синтаксис, например циклы управления, условные операторы и вызовы функций. Итак! Давайте посмотрим на общую идею этих подходов.

Разделяй и властвуй подход

Что кажется проще? Сломать сразу 10 палочек или по одной? Ответ очевиден, если вы не человек с огромной грубой силой. Здесь сломать 10 палочек - большая задача. Чтобы выполнить эту большую задачу, мы решили разбить ее на более мелкие подмножества, то есть ломать палочки одну за другой, чтобы достичь большей цели.

Алгоритмы «разделяй и властвуй» работают аналогичным образом. Они разбивают большие проблемы на подзадачи и решают их по отдельности, чтобы найти решение. Для этого в этих алгоритмах используется метод программирования, называемый рекурсией.

Процесс, в котором функция прямо или косвенно вызывает саму себя, называется рекурсией, а соответствующая функция называется рекурсивной функцией.

Эту технику можно разделить на следующие три части:

  1. Разделить. Это включает в себя разделение проблемы на более мелкие подзадачи.
  2. Победа. Решайте подзадачи, рекурсивно вызывая их до тех пор, пока они не будут решены.
  3. Объединение. Объедините подзадачи, чтобы получить окончательное решение всей проблемы.

Давайте рассмотрим пример сортировки любого целочисленного массива с использованием сортировки слиянием, алгоритма «разделяй и властвуй».

СОРТИРОВКА СЛИЯНИЕМ

Этот алгоритм сортировки делит входной массив на две половины и снова вызывает сам себя, чтобы разделить эти две половины на другие половины. Это продолжается до тех пор, пока массив не станет размером 1. Затем он сравнивает этот элемент размера 1 с другим элементом размера 1 и объединяет их в один массив. Этот процесс повторяется до тех пор, пока мы не получим отсортированный массив. На следующем рисунке показано, как работает алгоритм. Цифры обозначают этапы и последовательность действий, т. е. над каким массивом выполняется операция и когда.

Теперь вы, должно быть, думаете, зачем проходить такой утомительный процесс сортировки массива, когда вы можете просто использовать простые для понимания методы, такие как сортировка вставками. Разница заключается в количестве шагов, необходимых для получения конечного результата. Понятие под названием временная сложность используется для определения или сравнения того, какой алгоритм лучше другого для той же задачи, которой здесь является сортировка. Временная сложность в наихудшем случае для сортировки слиянием составляет O (nlogn), где n — количество элементов, присутствующих во входном массиве.

Другой алгоритм сортировки, использующий парадигму Разделяй и властвуй, — Быстрая сортировка.

Жадный подход

Чтобы понять жадный подход, давайте посмотрим на игру в бадминтон. Один игрок должен набрать очко против другого игрока, чтобы выиграть матч. Кроме того, они должны выиграть 2 из 3 матчей, чтобы выиграть игру. Здесь большая проблема состоит в том, чтобы выиграть игру, в то время как меньшая проблема состоит в том, чтобы выиграть очко у противника. Вы играете по текущей ситуации и не оглядываетесь на потерянные очки.

Это означает, что в некоторых случаях принятие решения, которое кажется правильным в данный момент, дает наилучшее решение. Техника жадности лучше всего подходит для наблюдения за непосредственной ситуацией. Жадные алгоритмы работают поэтапно. На каждом этапе принимается решение, хорошее на данный момент, не беспокоясь о будущем. Это означает, что выбирается какое-то местное лучшее. Он предполагает, что хороший локальный выбор обеспечивает глобальное оптимальное решение.

Два основных свойства оптимальных жадных алгоритмов:

  1. Свойство жадного выбора. Это свойство говорит о том, что глобально оптимальное решение может быть получено путем создания локально оптимального решения (жадного). Выбор, сделанный жадным алгоритмом, может зависеть от предыдущего выбора, но не от будущего. Он итеративно делает один жадный выбор за другим и сводит данную проблему к меньшей.
  2. Оптимальная подструктура. Проблема имеет оптимальную подструктуру, если оптимальное решение проблемы содержит оптимальные решения подзадач. Это означает, что мы можем решать подзадачи и создавать решения для решения более крупных проблем.

Для сравнения возьмем алгоритм сортировки, использующий жадный подход.

ВЫБОР СОРТИРОВКИ

Сортировка выбором — это алгоритм сортировки, который выбирает наименьший элемент из несортированного списка на каждой итерации и помещает этот элемент в начало несортированного списка.

Здесь мы устанавливаем первый элемент как минимум. Сравните минимум со вторым элементом. Если второй элемент меньше минимума, назначьте второй элемент как минимум. Сравните минимум с третьим элементом. Опять же, если третий элемент меньше, присвойте минимум третьему элементу, иначе ничего не делайте. Процесс продолжается до последнего элемента. После каждой итерации минимум помещается в начало несортированного списка. Для каждой итерации индексация начинается с первого несортированного элемента. Предыдущие шаги повторяются до тех пор, пока все элементы не будут размещены на своих местах.

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

Разделяй и властвуй против жадного подхода

  1. Подход D&C — это метод, основанный на решении, тогда как жадный подход — это подход к оптимизации.
  2. D&C может эффективно работать с задачами низкой сложности, такими как сортировка, тогда как жадный подход становится эффективным, когда сложность задач увеличивается, например, задача дробного рюкзака и сжатие кодирования Хаффмана.
  3. D&C реализует рекурсию для достижения решения, тогда как жадный использует итеративный подход для решения подзадач.
  4. D&C использует подход «сверху вниз», то есть разбивает большую проблему на более мелкие подзадачи, а затем решает их для построения решения. Жадный использует подход «снизу вверх», когда он сначала решает подзадачи, что приводит к оптимальному решению.
  5. Подход D&C носит рекурсивный характер, поэтому он медленнее, чем итеративный жадный подход.

Заключение

«Разделяй и властвуй» и «Жадность» — широко используемые парадигмы алгоритмов, которые находят применение в различных постановках задач. Мы не можем сказать, какой из них лучше, чем другой, поскольку это полностью зависит от проблемы. Надеюсь, этот блог дал вам представление о том, как работают эти парадигмы!