Описание тега recurrence

Описание тега Вопросы с тегом

Рекуррентное отношение - это уравнение, которое рекурсивно определяет последовательность после того, как заданы один или несколько начальных членов: каждый последующий член последовательности определяется как функция предыдущих членов.

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

Примером является последовательность Фибоначчи, которую можно определить как:
F(n) = F(n-1) + F(n-2), где F(0) = 1 и F(1) = 1.

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

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

Отношения рекуррентности имеют фундаментальное значение при анализе алгоритмов. В информатике повторение обычно возникает, когда мы анализируем сложность алгоритмов "разделяй и властвуй". Если алгоритм спроектирован таким образом, что он разбивает проблему на более мелкие подзадачи (разделяй и властвуй), время его работы описывается соотношением рекуррентности.

Для некоторых типичных рекуррентных соотношений асимптотический рост можно проанализировать с помощью основной теоремы.