Для любой произвольно двойной рекурсивной функции, как рассчитать время ее выполнения?
Например (в псевдокоде):
int a(int x){
if (x < = 0)
return 1010;
else
return b(x-1) + a(x-1);
}
int b(int y){
if (y <= -5)
return -2;
else
return b(a(y-1));
}
Или что-то вдоль этих линий.
Какие методы можно или нужно использовать, чтобы определить что-то подобное?
Ответы:
Вы продолжаете менять свою функцию. Но продолжайте выбирать те, которые будут работать вечно без преобразования ..
Рекурсия становится сложной, быстрой. Первый шаг к анализу предложенной дважды рекурсивной функции состоит в том, чтобы попытаться проследить ее по некоторым выборочным значениям, чтобы увидеть, что она делает. Если ваши вычисления попадают в бесконечный цикл, функция не является четко определенной. Если ваш расчет входит в спираль, которая продолжает получать большие числа (что происходит очень легко), это, вероятно, не очень хорошо определено.
Если прослеживание дает ответ, вы пытаетесь найти какую-то закономерность или рекуррентную связь между ответами. Если у вас есть это, вы можете попытаться выяснить его время выполнения. Выяснить это может быть очень, очень сложно, но у нас есть такие результаты, как теорема Мастера, которая позволяет нам найти ответ во многих случаях.
Помните, что даже с одной рекурсией легко придумать функции, время выполнения которых мы не знаем, как вычислить. Например, рассмотрим следующее:
В настоящее время неизвестно , является ли эта функция всегда четко определенной, не говоря уже о ее времени выполнения.
источник
Время выполнения этой конкретной пары функций бесконечно, потому что ни одна из них не возвращается без вызова другой. Возвращаемое значение
a
является всегда зависит от возвращаемого значения вызова ,b
который всегда вызываетa
... и то, что известно как бесконечная рекурсию .источник
a
только вызовы,b
если число передано> = 0. Но да, существует бесконечный цикл.Очевидный метод - запустить функцию и измерить, сколько времени это займет. Это только говорит вам, сколько времени занимает конкретный ввод, хотя. И если вы не знаете заранее, что функция завершается, сложно: нет механического способа выяснить, завершается ли функция - это проблема остановки , и она неразрешима.
Нахождение времени выполнения функции аналогично неразрешимо по теореме Райс . Фактически, теорема Райс показывает, что даже решение о том, работает ли функция во
O(f(n))
времени, неразрешимо.Поэтому лучшее, что вы можете сделать в целом, - это использовать свой человеческий интеллект (который, насколько мы знаем, не ограничен пределами машин Тьюринга) и попытаться распознать шаблон или изобрести его. Типичным способом анализа времени выполнения функции является преобразование рекурсивного определения функции в рекурсивное уравнение по времени ее выполнения (или набор уравнений для взаимно рекурсивных функций):
Что дальше? Теперь у вас есть математическая задача: вам нужно решить эти функциональные уравнения. Подход, который часто работает, состоит в том, чтобы превратить эти уравнения для целочисленных функций в уравнения для аналитических функций и использовать исчисление для их решения, интерпретируя функции
T_a
иT_b
как производящие функции .Что касается генерации функций и других вопросов дискретной математики, я рекомендую книгу Рональда Грэма, Дональда Кнута и Орен Паташник « Конкретная математика» .
источник
Как отмечали другие, анализ рекурсии может быть очень сложным и очень быстрым. Вот еще один пример такой вещи: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequence сложно вычислить ответ и время выполнения для них. Это связано с тем, что эти взаимно-рекурсивные функции имеют «сложную форму».
В любом случае, давайте посмотрим на этот простой пример:
http://pramode.net/clojure/2010/05/08/clojure-trampoline/
Давайте начнем с попытки вычислить
funa(m), m > 0
:Время выполнения:
Теперь давайте выберем другой, немного более сложный пример:
Вдохновленный http://planetmath.org/encyclopedia/MutualRecursion.html , который сам по себе является хорошим чтением, давайте посмотрим на: "" "Числа Фибоначчи можно интерпретировать с помощью взаимной рекурсии: F (0) = 1 и G (0 ) = 1, где F (n + 1) = F (n) + G (n) и G (n + 1) = F (n). "" "
Итак, что такое время выполнения F? Мы пойдем другим путем.
Ну, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Теперь R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Нетрудно видеть, что R (F (m)) = F (m) - например, количество вызовов функций, необходимых для вычисления числа Фибоначчи по индексу i, равно значению числа Фибоначчи по индексу я. Предполагалось, что сложение двух чисел намного быстрее, чем вызов функции. Если бы это было не так, то это было бы верно: R (F (1)) = R (F (0)) + 1 + R (G (0)), и анализ этого был бы более сложным, возможно без простого решения в закрытой форме.
Закрытую форму для последовательности Фибоначчи не обязательно легко изобрести заново, не говоря уже о некоторых более сложных примерах.
источник
Первое, что нужно сделать, это показать, что функции, которые вы определили, завершаются и для каких значений точно. В примере, который вы определили
b
заканчивается толькоy <= -5
потому, что если вы включите любое другое значение, то у вас будет термин формыb(a(y-1))
. Если вы немного расширитесь, вы увидите, что термин формы вb(a(y-1))
конечном итоге приводит к термину,b(1010)
который приводит к термину,b(a(1009))
который снова приводит к терминуb(1010)
. Это означает, что вы не можете вставить любое значение,a
которое не удовлетворяет,x <= -4
потому что, если вы это сделаете, вы получите бесконечный цикл, где вычисляемое значение зависит от вычисляемого значения. По сути, этот пример имеет постоянное время выполнения.Таким образом, простой ответ заключается в том, что не существует общего метода для определения времени выполнения рекурсивных функций, потому что нет общей процедуры, которая определяет, завершается ли рекурсивно определенная функция.
источник
Время выполнения как в Big-O?
Это просто: O (N) - при условии, что есть условие завершения.
Рекурсия - это просто цикл, а простой цикл - это O (N), независимо от того, сколько операций вы делаете в этом цикле (а вызов другого метода - это просто еще один шаг в цикле).
Интересно, если у вас есть цикл внутри одного или нескольких рекурсивных методов. В этом случае у вас получится какая-то экспоненциальная производительность (умножение на O (N) при каждом прохождении метода).
источник
O(2^n)
иO(n*log(n))
, соответственно.a
вызовыb
иb
вызовы методов,a
так что вы не можете просто предположить, что любой метод занимает времяO(1)
.