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

Делить

Раздел «Разделение» фокусируется на разделении большой проблемы на более мелкие и более управляемые подзадачи. Этот процесс постоянно разбивает проблему на более мелкие проблемы, что известно как рекурсивный случай, пока подзадачи не станут достаточно маленькими. базовый случай - это когда для подзадачи больше не требуется рекурсия. Например, давайте посмотрим на псевдокод для быстрой сортировки.

// pseudocode for quick sort
quicksort(int[] arr, int low, int high) {
  
  if (low < high) {
    int p = partition(arr, low, high);
    
    quicksort(arr, low, p - 1); // calling the lower half
    quicksort(arr, p + 1, high); // calling the upper half
  }
}
// pseudocode for partition that makes all smaller numbers in front // of the pivot and all bigger numbers behind the pivot
partition (int arr[], int low, int high) {
  // pivot (Element to be placed at right position)
  pivot = arr[high];  
 
  int i = (low - 1)  // Index of smaller element

  for (j = low; j <= high - 1; j++) {
    // If current element is smaller than the pivot
    if (arr[j] < pivot) {
      ++i;    
      swap(arr[i] and arr[j])
    }
  }
  swap(arr[i + 1] and arr[high])
  return (i + 1)
}

Как видите, он вызывает quicksort в своей собственной функции. Это рекурсивный случай. Базовый случай неявно интерпретируется в условном выражении quicksort, так что, когда условие не выполняется, делать нечего.

Завоевывать

Базовый вариант - это цель. При разбиении проблемы на более мелкие проблемы она начнет решаться, когда станет достаточно маленькой и больше не потребуется рекурсия. Это победная часть. Как вы можете видеть в примере, базовый вариант будет считаться условным в quicksort. Если это условие не выполняется, в этой ветви вызовов больше не вызывается рекурсия. Пришло время объединить решение этой ветви вызовов с другой ветвью вызовов.

В примере quicksort вы можете видеть, что каждый раз, когда вызывается quicksort, вызывается функция partition. Это та часть, где решается или преодолевается подзадача, а затем объединяется с другими подрешениями.

Объединение

Комбинирующая часть важна, потому что, несмотря на то, что меньшие проблемы решаются, чтобы получить решение большой проблемы, меньшие должны быть объединены. Часть комбинирования немного менее заметна в quicksort, потому что мы работаем с массивом, который включает передачу по ссылке. Решения подзадач вносят прямые изменения в массив при решении более мелких проблем, которые в конечном итоге сортируют весь массив. Объединение более очевидно в чем-то вроде решения последовательности Фибоначчи для n-го члена, который имеет рекурсивное возвращаемое значение fib(n — 1) + fib(n — 2). Здесь каждое подрешение явно объединено в функции.

Заключительные замечания

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