Разделяй и Властвуй. Разбор задач12.01.2022 14:16

Решение задач с помощью метода «Разделяй и Властвуй» или по-английски «Divide and Conquer» является одним из базовых методов по ускорению алгоритмов. Примером тому служит переход от квадратичной сложности пузырьковой сортировки или сортировки вставками к сложности $\inline O(n\log{n})$ при сортировке слиянием. Или переход от линейной сложности к логарифмической, при реализации поиска элемента в отсортированном массиве (см. бинарный поиск).

В этой статье мы рассмотрим два примера задач с пояснениями и кодом, в которых будет использоваться этот подход.

Для начала сформулируем, разделение и властвование. Решение задачи с помощью данного подхода обладает следующими тремя свойствами:

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

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

Задача №1

Дан унимодальный массив, состоящий из $\inline n$ уникальных элементов. Будем называть массив унимодальным, если его элементы, стоящие до максимума, расположены в порядке возрастания, а элементы, стоящие после максимума, расположены в порядке убывания. Требуется предоставить алгоритм, возвращающий максимальный элемент такого массива за логарифмическое ( $\inline O \left(\log n \right)$ ) время.

Решение

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

max = arr[0]
for item in arr[1:]:
  if item > max:
    max = item

Когда массив будет исчерпан, в переменной max будет записан наибольший из элементов. Сложность такого подхода эквивалентна линейной, поскольку необходимо просмотреть каждый элемент из $\inline n$ возможных.

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

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

Указанные выше свойства отвечают на два вопроса: «что мы ищем в массиве» и «в каком подмножестве массива мы это ищем». Чтобы ответить на вопрос: «как мы выбираем очередной рассматриваемый элемент», воспользуемся тем фактом, что максимум лежит где-то внутри массива, и будем принимать к рассмотрению серединный элемент в очередном подмножестве.

def unimodal_max(arr, low, high):
    # если в результате разбиения подмножество состоит из одного элемента, 
    # то возвращаем этот элемент
    if low == high:
        return arr[low]
    
    # если в результате разбиения подмножество состоит из двух элементов, 
    # то возвращаем максимум из них
    if high - low == 1:
        if arr[low] >= arr[high]:
            return arr[low]
        else:
            return arr[high]
    
    # "базовый случай": при длине подмножества большем двух, 
    # рассматриваем серединный элемент (см. свойство 1)
    mid = (low + high) // 2
    if arr[mid] > arr[mid + 1] and arr[mid] > arr[mid - 1]:
        return arr[mid]
    
    # если серединный элемент не оказался искомым, 
    # то продолжаем поиск максимума только, 
    # где имеет смысл (см. свойство 2)
    if arr[mid - 1] > arr[mid] > arr[mid + 1] :
        return unimodal_max(arr, low, mid-1)
    else:
        return unimodal_max(arr, mid + 1, high)

# пример вызова: 
# assert(unimodal_max([0,1,2,3,4,5,10,9,8,7,6]) == 10)

Оценка сложности

При первом запуске данного алгоритма, если его длина больше трёх, и если серединный элемент не оказался искомым, то независимо от того, как велико $\inline n$ , следующий вызов будет работать только с $\inline \frac{n}{2}$ элементами, среди которых максимум должен найтись по свойству 2. Во время второго и всех последующих вызовов этого алгоритма количество элементов, принимаемых к рассмотрению, сокращается вдвое. Этот процесс продолжается до тех пор, пока не будет выполнен базовый случай по количеству элементов (два и менее элементов), либо базовый случай из свойства 1.

Деление массива надвое до достижения базового случая не может продолжаться больше, чем $\inline \log_{2}{n}$ раз, а в каждый из этих вызовов совершается константное, не зависящее от $\inline n$ число операций. Отсюда следует вывод, что сложность представленного алгоритма $\inline O \left(\log n \right)$ .

Задача №2

Дан неупорядоченный массив из $\inline n$ элементов, где $\inline n$ является степенью двойки. Требуется предоставить алгоритм, который находит второй по велечине элемент массива, осуществляя не более $\inline n + \log_{2}{n} - 2$ операций сравнения.

Решение

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

Будем проходить по массиву и поддерживать два числа max и second_largest.

# будем считать, что в массиве более 2х элементов
max = arr[0]
if arr[1] > max:
  max = arr[1]
  second_largest = arr[0]
else:
  second_largest = arr[1]
for item in arr[2:]:
  # если очередной элемент больше обоих максимумов,
  # обновляем их оба
  if item > max:
    second_largest = max
    max = item
  # если больше только второго максимума,
  # то обновляем его
  elif item > second_largest:
    second_largest = item

Подсчитаем количество сравнений

Лучшим возможным вариантом может быть $\inline n-1$ сравнение. Происходит это, когда условие первого if выполняется на каждой итерации цикла (это даёт $\inline n-2$ сравнения), и добавляется одно сравнение до цикла. Такое поведение может быть достигнуто на упорядоченном по возрастанию массиве.

Рассмотрим убывающий массив. В этом случае сравнение в if выполняется каждую итерацию, но управление передаётся в ветку elif, где также выполняется еще одно сравнение. Получается, что суммарно операций сравнения в случае убывающего массива, с учетом первого сравнения до цикла, будет равняться $\inline 2n-3$ .

Как можно сократить это близкое к $\inline 2n$ операций число до $\inline n + \log_{2}{n} - 2$ ? Попробуем искать максимум, путём разбиения доступных элементов на две части и последующего поиска наибольших значений в них.

Рассмотрим массив, состоящий из элементов 9, 18, 3, 5, 25, 1, 5, 19. Зеленым цветом на диаграме выделен максимум этих чисел. Смотря снизу вверх, видно, что максимум находится путём сравнений двух чисел, наибольших в своём подмножестве.

В этом случае количество сравнений для поиска максимума равно сумме: $\inline n/2 + n/4 + n/8 + ... + 1 = n-1$ . Чтобы найти second_largest, потребуется рассмотреть все элементы, с которыми сравнивался max (на диаграмме они выделены желто-оранжевым). Поиск максимального среди них потребует $\inline \log_{2}{n} - 1$ операцию, поскольку элементов в этом маленьком списке не больше, чем глубина дерева минус один.

Осталось только реализовать этот алгоритм:

def second_largest(arr):
    # функция find_max_comp выполняет поиск максимума в массиве,
    # по принципу на диаграмме
    # кроме этого, в ней осуществляется поддержка списка элементов,
    # с которыми максимум сравнивался
    def find_max_comp(low, high, arr):
            if low >= high:
                return arr[low], []
            mid = (high + low) // 2
            x, lst_x = find_max_and_comp(low, mid, arr)
            y, lst_y = find_max_and_comp(mid + 1, high, arr)
            if x > y:
                lst_x.append(y)
                return x, lst_x
            else:
                lst_y.append(x)
                return y, lst_y
    
    # для определения второго по величине элемента, 
    # требуется вычислить список рассмотренных с наибольшим элементов,
    # а затем найти максимум среди них
    comparisons = find_max_and_comp(0, len(arr) - 1, arr)[1]
    return find_max_and_comp(0, len(comparisons) - 1, comparisons)[0]

Количество операций сравнения алгоритма выше как раз равно $\inline n + \log_{2}{n} - 2$ . Этот факт можно показать в числах, если завести глобальную переменную — счетчик.

Заключение

Подход к решению задач — «Разделяй и Властвуй» не является самым простым концептом в программировании, но зато его легко идентифицировать. Зачастую, когда требуется решить задачу поиска объекта среди других объектов с заданной логарифмической сложностью, скорее всего от вас ожидают применения этого подхода, основанного на рекурсивных вызовах на двух подможествах данных. Это не правило, но два подтверждения этой гипотезе мы разобрали в этой статье.

Информация

[1] Условия задач взяты из книги «Algorithms Illuminated: Part 1: The Basics» от Tim Roughgarden. [2] Решения авторские.

Данную статью я подготовил в преддверии старта курса «Алгоритмы и структуры данных» от OTUS. Узнать подробнее о курсе можно тут.