Мастер-метод позволяет прямо определить асимптотическую сложность алгоритмов «разделяй и властвуй» вида
T(n) = aT(n/b) + f(n)
В основном вы должны помнить три случая:
Подробнее об использовании метода Master можно прочитать здесь.
В этой статье мы попытаемся увидеть интуицию, лежащую в основе метода Master, на нескольких упрощенных примерах. Позже, когда мы пройдем формальное доказательство теоремы Мастера, мы увидим, что эти упрощения не имеют значения. Но сначала давайте посмотрим, почему мы имеем дело с логарифмическими функциями во всех трех случаях.
Что со всеми логарифмами?
В рекурсивных алгоритмах мы можем использовать деревья рекурсии для визуализации шагов алгоритма. Для повторения формы:
T(n) = 2T(n/2) + 𝚹(n)
В итоге мы получим дерево рекурсии, похожее на:
Дерево продолжает расти до тех пор, пока n не станет достаточно маленьким, чтобы его можно было решить без дальнейшей рекурсии. Мы называем это базовым случаем. Предполагается, что базовый случай решается за постоянное время c. После достижения базового случая дерево начинает сжиматься, поскольку результаты на более низком уровне объединяются, чтобы сформировать решение для родительских узлов. Это будет продолжаться до тех пор, пока мы не доберемся до корня, который даст нам решение исходной проблемы. Таким образом, общая стоимость решения задачи размера n составляет:
Total cost = cost(base cases) + cost(division+combination)
Стоимость обработки объединения или разделения подзадач обозначается 𝚹(n). Таким образом, для подзадачи размера n/4 стоимость разделения входных данных на 2 подзадачи размера n/8 и последующего объединения результатов для решения размера n/4 составляет cn/4.
Сколько базовых случаев существует?
Предположим, что входной размер равен степени числа 2. Таким образом, наше дерево рекурсии будет полным двоичным деревом. На каждом уровне мы делим каждый узел на двух детей. Есть один корневой узел, назовем его корневым уровнем 0. Корневой узел делится на 2 дочерних узла на уровне 1. Каждый из узлов на уровне 1 делится на 2 дочерних, таким образом, мы получим 4 узла на уровне 2. вы видите здесь закономерность?
На уровне x дерева есть 2 узла. Итак, сколько базовых случаев существует? Нам просто нужно вычислить высоту дерева, h, и вычислить 2ʰ.
Высота дерева рекурсии
Мы достигли базовых случаев, когда размер подзадачи был некоторой константой c. В качестве еще одного упрощения предположим, что в базовом случае размер подзадачи равен 1.
Для каждого уровня, на который мы опускаемся, мы вдвое уменьшаем размер подзадачи. Таким образом, на уровне x мы будем иметь дело с подзадачами размера n/2ˣ.
Решая следующее уравнение, мы можем вычислить высоту дерева рекурсии.
Итак, теперь, когда мы знаем высоту дерева, мы можем легко вычислить количество базовых случаев.
Поскольку мы используем T(n) = 2T(n/2) + 𝚹(n) в качестве примера, у нас есть a=2 и b=2. Заменив a и b в приведенной выше формуле, мы получим формулу для расчета количества базовых случаев для любого повторения.
Это выглядит знакомо! Каждый из вариантов дерева метода Master выполняет какое-то сравнение с аналогичной функцией. Как вы можете догадаться, в каждом случае общая стоимость решения базовых случаев сравнивается со стоимостью разделения и объединения результатов подзадач.
Давайте рассмотрим случаи Мастер-метода и посмотрим, сможем ли мы увидеть интуицию, стоящую за ними.
Случай 1: в общей стоимости преобладает стоимость решения базовых случаев.
Первый случай применяется, когда функция вычисления стоимости решения базовых случаев полиномиально и асимптотически больше, чем функция вычисления стоимости объединения и деления. Таким образом, асимптотическая сложность повторения:
Случай 2: общая стоимость равномерно распределена по уровням дерева.
Второй случай применяется, когда каждый уровень дерева вносит долю в общую стоимость, и затраты распределяются равномерно. Каждый уровень дерева вносит f(n) в общую стоимость, а существует lg n уровней, поэтому общая стоимость составляет:
Случай 3: в общей стоимости преобладает стоимость корня
Третий случай применяется, когда функция вычисления стоимости объединения и деления корня полиномиально и асимптотически больше, чем функция вычисления стоимости решения нижних уровней задачи. дерево. Таким образом, асимптотическая сложность повторения:
В этой статье мы увидели интуицию, стоящую за методом Мастера. В следующих статьях мы рассмотрим формальное доказательство метода Мастера и докажем, что упрощения, которые мы сделали в этой статье, в конечном итоге не имеют значения.
