Алгоритмы (теория/практика): Часть 6.1. «Разделяй и властвуй»

Чтобы не плодить лонгриды, я разбил материал на две части.

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

Мы показали также, что сложность двоичного поиска равняется \(\Theta (\log _{ 2 }{ n })\), где \(n\) – это размер входных данных. Разумеется, это не единственный пример, и мы рассмотрим целый класс алгоритмов, реализуемых с помощью парадигмы «разделяй и властвуй».

Это довольно любопытное название точно определяет механизм работы. Действительно, алгоритм заставляет нас на каждом шаге разделить входной массив на небольшие части и продолжить работу лишь с ними. На самом деле, применение метода «разделяй и властвуй» не ограничивается делением только на две части, поэтому ничто не мешает вам разбить задачу на 4 или 8 частей, если это необходимо. В общем случае, этот класс алгоритмов на каждом этапе выполняет следующие действия:

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

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

Большая часть подобных задач решается с применением рекурсии, а её очень удобно анализировать с помощью рекуррентных соотношений. Рекуррентное соотношение – уравнение или неравенство, которое описывает функцию через её значения для меньших аргументов (определение из книги «Алгоритмы. Построение и анализ»).

Двоичный поиск

Мы уже несколько раз его встречали, поэтому будем рассматривать именно его. На всякий случай в очередной раз приведу его (далеко не самый идеальный) код:

int binary_search(int arr[], int start, int end, int target)
{
    if (start == end)
    {
        return arr[start] == target ? start : -1;
    }

    int mid = floor(start + (end - start) / 2);

    if (target <= arr[mid]) 
    { 
        // Левая часть 
        return binary_search(arr, start, mid, target); 
    } 
    else 
    { 
        // Правая часть 
        return binary_search(arr, mid + 1, end, target); 
    } 
} 

Как уже было сказано, на каждом шаге происходит минимум три действия: разделение (массив разделяется на левую и правую части), властвование (происходит сравнение искомого значения, а также рекурсивные вызовы) и комбинирование (при достижении единичного массива стартует терминальная (завершающая) ветвь рекурсии и значение возвращается).

Мы уже попытались интуитивно проанализировать этот алгоритм и даже сумели сделать вывод о его сложности. Теперь давайте сделаем это немного красивее.

Обозначим через \(T(n)\) время выполнения алгоритма для массива из n элементов. Тогда \(T({ n }/{ 2 })\) будет описывать время для половины массива. В каждом рекурсивном вызове алгоритм выполняет определенные операции, поэтому обозначим их все через \(\Theta (1)\). Это обозначение описывает некоторую функцию, которая выполняется за константное время, независимое от \(n\).

Итак, данный алгоритм можно описать с помощью следующего рекуррентного соотношения:

Как видно, у соотношения есть два случая, первый из которых называется базовым. Он используется, когда цепочка рекурсивных вызовов доходит до единичного массива. Второй случай называется рекурсивным, первый член которого как раз и показывает, что исходная задача сокращается вдвое, затем используется в той же самой функции до тех пор, пока цепочка рекурсий не достигнет базового случая. Второй член описывает всё то, что выполняет алгоритм в каждом вызове (например, операции сравнения). Мы используем обозначение пола (округления в меньшую сторону – \(\left\lfloor \right\rfloor \)) для ситуаций, когда исходное \(n\) не является степенью числа 2.

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

Метод подстановки

Хорошо, мы составили рекуррентное соотношение. Теперь нам нужно решить его. Для этого существует несколько стратегий.

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

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

Метод подстановки удобно применять для нахождения верхней или нижней границы сложности. Однако, найдя их, мы можем сделать вывод и об асимптотически точной оценке.

Итак, предположим, что решением нашего рекуррентного соотношения является \(\Theta (\log _{ 2 }{ n })\). Мы помним, что \(f\left( n \right) =\Theta (g\left( n \right) )\) тогда, когда \(f\left( n \right) =O(g\left( n \right) )\) и \(f\left( n \right) =\Omega (g\left( n \right) )\).

Давайте покажем, что \(T\left( n \right) =O (\log _{ 2 }{ n })\). Для этого нам нужно найти константу \(c\) при которой будет справедливо неравенство:

Первым делом покажем справедливость решения для граничных условий. В нашем соотношении только одно граничное условие (при \(n=1\)), поэтому давайте сделаем это. Просто подставим 1 вместо n и получим:

Логарифм единицы равен нулю, поэтому вся правая часть обернётся в ноль, что не совсем похоже на то, чего мы ожидали. Но мы обратимся к нашему определению \(O\)-обозначения и увидим, что неравенство \(T\left( n \right) \le c\log _{ 2 }{ n }\) должно выполняться для некоторой константы \(c>0\) и \(n>{ n }_{ 0 }\). Ничто не мешает сдвинуть нам базу на пару единиц и доказать справедливость. Важно понимать, что базовый случай в рекуррентном соотношении не обязательно должен совпадать с базой индукции.

Например, для \(n\ge 2\) и \(c\ge 2\) неравенство будет верным.

Внимательность: Еще раз хочу сделать акцент на том, что база индукции и база рекуррентного соотношения не обязательно должны совпадать. Мы пытаемся доказать, что асимптотически верхней границей нашего алгоритма является некоторая функция. При этом определение \(О\)-обозначения говорит, что неравенство должно соблюдаться для некоторого \({ n }_{ 0 }\). Поэтому совершенно ничто не мешает нам выбрать такое \({ n }_{ 0 }\), чтобы базовый случай выполнялся. Это, конечно же, хитрость, но она ничему не противоречит.

Хорошо, теперь проверим рекурсивный случай. Рекуррентные соотношения выражают функцию через её значения для меньших аргументов, поэтому нам нужно доказать, что данное неравенство справедливо для \(\left\lfloor { n }/{ 2 } \right\rfloor \). В этом случае наше оно примет следующий вид:

Теперь подставим получившееся в рекурсивный случай нашего рекуррентного соотношения и докажем справедливость получившегося неравенства (отбросим 0, так как он связан с базовым случаем):

Воспользуемся свойством логарифмов (избавимся также от округления, так как \(n\) в любом случае является целым числом):

В итоге получается вот это:

Неравенство справедливо для всех \(c\ge 1\).

Здесь на место \(\Theta (1)\) я подставил единицу. В сущности, это не так важно, так как тут может быть любое константное значение. Нам важно показать, что в принципе возможно найти такое значение \(c\), при котором неравенство будет выполняться, само же значение нас не сильно волнует.

Тем же способом покажем и то, что \(T(n)=\Omega (\log _{ 2 }{ n } )\). Для этого просто убедимся, что есть некоторая константа \(c>0\) такая, что будет справедливо неравенство:

А оно таковым будет, например, при \(c=\frac { 1 }{ 2 } \). С базовым случаем тоже всё просто, подставив единицу мы получим, что \(T(1)\ge 0\). Здесь уже всё верно.

Мы показали, что \(T(n)=O({ log }_{ 2 }n)\) и \(T(n)=\Omega ({ log }_{ 2 }n)\), а отсюда можно сделать вывод, что \(T(n)=\Theta ({ log }_{ 2 }n)\).

С этим всё. Как видно, это довольно простой способ найти сложность алгоритма. Тем не менее, необходимость угадывания решения выглядит не слишком привлекательно. Неужели нет альтернативы? Конечно же есть! И следующей части мы рассмотрим еще два способа решения рекуррентных соотношений.

Следующая статья

Предыдущая статья