Как определить время выполнения двойной рекурсивной функции?

15

Для любой произвольно двойной рекурсивной функции, как рассчитать время ее выполнения?

Например (в псевдокоде):

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));
}

Или что-то вдоль этих линий.

Какие методы можно или нужно использовать, чтобы определить что-то подобное?

if_zero_equals_one
источник
2
Это домашнее задание?
Бернард
5
Нет, это летнее время, и я люблю учиться. Я полагаю, что впереди, вместо того чтобы позволить мозгу превратиться в кашу.
if_zero_equals_one
11
Хорошо, понял. Для тех, кто голосует за перенос этого в переполнение стека: это здесь по теме и не по теме переполнение стека. Programmers.SE - для концептуальных, интерактивных вопросов; Переполнение стека предназначено для вопросов, возникающих при реализации.
3
Спасибо, вот почему я сделал это здесь, в первую очередь. Кроме того, лучше знать, как ловить рыбу, чем получать рыбу.
if_zero_equals_one
1
В этом частном случае это все еще вообще бесконечная рекурсия, потому что b (a (0)) вызывает бесконечно много других b (a (0)) членов. Это было бы иначе, если бы это была математическая формула. Если бы у вас были другие настройки, все было бы иначе. Как и в математике, у некоторых задач есть решение, у некоторых - нет, у некоторых - простое, у некоторых - нет. Существует много взаимно рекурсивных случаев, когда решение существует. Иногда, чтобы не взорвать стек, нужно было использовать трамплин.
Работа

Ответы:

11

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

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

Если прослеживание дает ответ, вы пытаетесь найти какую-то закономерность или рекуррентную связь между ответами. Если у вас есть это, вы можете попытаться выяснить его время выполнения. Выяснить это может быть очень, очень сложно, но у нас есть такие результаты, как теорема Мастера, которая позволяет нам найти ответ во многих случаях.

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

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

В настоящее время неизвестно , является ли эта функция всегда четко определенной, не говоря уже о ее времени выполнения.

btilly
источник
5

Время выполнения этой конкретной пары функций бесконечно, потому что ни одна из них не возвращается без вызова другой. Возвращаемое значение aявляется всегда зависит от возвращаемого значения вызова , bкоторый всегда вызывает a... и то, что известно как бесконечная рекурсию .

jimreed
источник
Не ищу конкретные функции прямо здесь. Я ищу общий способ найти время выполнения рекурсивных функций, которые вызывают друг друга.
if_zero_equals_one
1
Я не уверен, что есть решение в общем случае. Чтобы Big-O имел смысл, вы должны знать, остановится ли когда-нибудь алгоритм. Существуют некоторые рекурсивные алгоритмы, в которых необходимо выполнить вычисление, прежде чем вы узнаете, сколько времени это займет (например, определение, принадлежит ли точка к набору мандлеброт или нет).
Jimreed
Не всегда, aтолько вызовы, bесли число передано> = 0. Но да, существует бесконечный цикл.
btilly
1
@btilly пример был изменен после того, как я опубликовал свой ответ.
Jimreed
1
@jimreed: И это снова изменилось. Я бы удалил свой комментарий, если бы мог.
btilly
4

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

Нахождение времени выполнения функции аналогично неразрешимо по теореме Райс . Фактически, теорема Райс показывает, что даже решение о том, работает ли функция во O(f(n))времени, неразрешимо.

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

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

Что дальше? Теперь у вас есть математическая задача: вам нужно решить эти функциональные уравнения. Подход, который часто работает, состоит в том, чтобы превратить эти уравнения для целочисленных функций в уравнения для аналитических функций и использовать исчисление для их решения, интерпретируя функции T_aи T_bкак производящие функции .

Что касается генерации функций и других вопросов дискретной математики, я рекомендую книгу Рональда Грэма, Дональда Кнута и Орен Паташник « Конкретная математика» .

Жиль "ТАК - перестань быть злым"
источник
1

Как отмечали другие, анализ рекурсии может быть очень сложным и очень быстрым. Вот еще один пример такой вещи: 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/

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Давайте начнем с попытки вычислить funa(m), m > 0:

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

Время выполнения:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

Теперь давайте выберем другой, немного более сложный пример:

Вдохновленный 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)), и анализ этого был бы более сложным, возможно без простого решения в закрытой форме.

Закрытую форму для последовательности Фибоначчи не обязательно легко изобрести заново, не говоря уже о некоторых более сложных примерах.

работа
источник
0

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

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));
}

bзаканчивается только y <= -5потому, что если вы включите любое другое значение, то у вас будет термин формы b(a(y-1)). Если вы немного расширитесь, вы увидите, что термин формы в b(a(y-1))конечном итоге приводит к термину, b(1010)который приводит к термину, b(a(1009))который снова приводит к термину b(1010). Это означает, что вы не можете вставить любое значение, aкоторое не удовлетворяет, x <= -4потому что, если вы это сделаете, вы получите бесконечный цикл, где вычисляемое значение зависит от вычисляемого значения. По сути, этот пример имеет постоянное время выполнения.

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

davidk01
источник
-5

Время выполнения как в Big-O?

Это просто: O (N) - при условии, что есть условие завершения.

Рекурсия - это просто цикл, а простой цикл - это O (N), независимо от того, сколько операций вы делаете в этом цикле (а вызов другого метода - это просто еще один шаг в цикле).

Интересно, если у вас есть цикл внутри одного или нескольких рекурсивных методов. В этом случае у вас получится какая-то экспоненциальная производительность (умножение на O (N) при каждом прохождении метода).

скоро
источник
2
Вы определяете производительность Big-O, беря самый высокий порядок любого вызываемого метода и умножая его на порядок вызывающего метода. Однако, как только вы начнете говорить об экспоненциальной и факторной производительности, вы можете проигнорировать полиномиальную производительность. Я считаю, что то же самое справедливо при сравнении экспоненциальных и факторных: факторные победы. Мне никогда не приходилось анализировать систему, которая была бы как экспоненциальной, так и факторной.
Anon
5
Это неверно Рекурсивными формами вычисления n-го числа Фибоначчи и быстрой сортировки являются O(2^n)и O(n*log(n)), соответственно.
unpythonic
1
Не делая каких-либо фантастических доказательств, я бы хотел направить вас на amazon.com/Introduction-Algorithms-Second-Thomas-Cormen/dp/… и попытаться взглянуть на этот сайт SE cstheory.stackexchange.com .
Брайан Харрингтон
4
Почему люди проголосовали за этот ужасно неправильный ответ? Вызов метода занимает время, пропорциональное времени, которое занимает метод. В этом случае aвызовы bи bвызовы методов, aтак что вы не можете просто предположить, что любой метод занимает время O(1).
btilly
2
@Anon - Автор запрашивал произвольно двойную рекурсивную функцию, а не только ту, которая показана выше. Я привел два примера простой рекурсии, которые не соответствуют вашему объяснению. Это тривиальное преобразование старых стандартов в «двойную рекурсивную» форму, которая была экспоненциальной (соответствует вашему предупреждению), а другая - нет (не охвачена).
unpythonic