Рекуррентные соотношения

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

Definition

Рекуррентное соотношение — это уравнение, которое определяет значение функции для данного входного значения через её значения для меньших входных значений; при анализе алгоритмов оно выражает стоимость алгоритма для входных данных размера n через его стоимость для меньших подзадач.

Scope

Эта тема охватывает формулировку и решение рекуррентных соотношений, возникающих при анализе алгоритмов: метод подстановки, метод дерева рекурсии и основную теорему для рекуррентных соотношений типа «разделяй и властвуй» вида T(n) = aT(n/b) + f(n). Объясняется, как каждый рекурсивный алгоритм порождает рекуррентное соотношение и как преобразовать это соотношение в границу «большая тета». Исключается само асимптотическое обозначение, которое рассматривается отдельно, а также методы комбинаторных производящих функций из дискретной математики.

Core questions

• Как рекурсивный алгоритм порождает рекуррентное соотношение для своего времени выполнения?
• Как используется метод подстановки для доказательства и проверки предполагаемого решения?
• Как метод дерева рекурсии выявляет общую работу на разных уровнях рекурсии?
• Когда применима основная теорема и что означают её три случая?
• Как обрабатываются рекуррентные соотношения, которые не подпадают под форму основной теоремы?

Key concepts

• рекуррентное соотношение
• метод подстановки
• метод дерева рекурсии
• основная теорема
• рекуррентное соотношение типа «разделяй и властвуй»
• базовый случай и рекурсивный случай
• решение в замкнутой форме
• метод Акры-Баззи

Key theories

Основная теорема

Для рекуррентных соотношений типа «разделяй и властвуй» T(n) = aT(n/b) + f(n) основная теорема даёт асимптотическое решение путём сравнения f(n) с n, возведённым в степень логарифма по основанию b от a, охватывая три случая, когда доминируют листья, корень или сбалансированные уровни.

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

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

Clinical relevance

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

History

Анализ рекуррентных соотношений в алгоритмах был систематизирован в книге Кнута «Искусство программирования». Основная теорема стала основным элементом учебников благодаря CLRS, а метод Акры-Баззи (1998) обобщил её на более широкий класс рекуррентных соотношений типа «разделяй и властвуй» с неравномерным разбиением.

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

Когда я могу использовать основную теорему?

Основная теорема применима к рекуррентным соотношениям вида T(n) = aT(n/b) + f(n) при a >= 1 и b > 1, где каждый уровень разбивает задачу на a подзадач размера n/b. Рекуррентные соотношения с неравномерным разбиением, переменными размерами подзадач или неполиномиальными затратами на объединение могут потребовать использования методов дерева рекурсии, подстановки или Акры-Баззи.

Почему рекуррентное соотношение сортировки слиянием даёт O(n log n)?

Сортировка слиянием даёт T(n) = 2T(n/2) + O(n): две подзадачи половинного размера плюс линейное слияние. Здесь работа на каждом уровне одинакова для всех log n уровней дерева рекурсии, поэтому общая сумма составляет n умножить на log n, что основная теорема подтверждает как Theta(n log n).