Рекуррентное отношение для гипотетической рекурсивной функции

Каков метод определения сложности времени для рекурсивных программ? Давайте рассмотрим этот код.Рекуррентное отношение для гипотетической рекурсивной функции

int hypo(int a, int n) 
{ 
    if(n == 1) 
     return 0; 
    else 
     return a + hypo(a,n-1) * hypo(a,n-1); 
}

источник

2015-01-27 manali sikdar

Вычислите стоимость одного выполнения 'hypo' (без рекурсивных вызовов) и выясните, сколько раз метод будет называться рекурсивно. – MAV

В общем, вы должны делать то, что сказал @MAV, но ваш пример ужасен, вместо возврата hypo (a, n-1) * hypo (a, n-1) просто найдите b = hypo (a, n-1) ; return b * 2. у вас код должен иметь сложную сложность времени 2^n, но если вам нравится то, что я сказал не только, это было бы полиномиально, но и было бы линейным;) – Lrrr

В основном с вашим кодом время для получения hypo (a, n) это время, чтобы получить hypo (a, n-1) дважды. то есть. t (a, n) = 2 * t (a, n-1) также t (a, 1) в основном 1 оттуда вы можете получить сложность – user189

Первое, что вам нужно сделать, это написать уравнение, определяющее время работы (это часто бывает просто и не требует никакого решения). В вашем примере, вы обозначите через f(a, n) время выполнения функции для параметров a и n, а затем:

f(a, n) не зависит от a, так что давайте писать его f(n) вместо
f(1) постоянный ; давайте обозначим его через k
Если n > 1f(n) = c + 2 * f(n-1), то, где c является константой (еще один)

Итак, теперь вы должны выяснить, какая функция удовлетворяет уравнениям f(n) = c + 2 * f(n-1) и f(1) = k. Там нет общего метода, но в вашем случае это легко вычислить f(2), f(3) ...:

f(2) = c + 2 * f(1) =  c + 2 * k 
f(3) = c + 2 * f(2) = 3 * c + 4 * k 
f(4) = c + 2 * f(3) = 7 * c + 8 * k 
f(5) = c + 2 * f(4) = 15 * c + 16 * k

Это кажется довольно легко найти f(n) отсюда (вы можете доказать формулу по индукции, или просто сказать "это очевидно").

источник

2015-01-27 17:49:36 anatolyg

Наиболее простые проблемы этой формы могут быть решены с помощью основной теоремы. См. http://en.wikipedia.org/wiki/Master_theorem.

Более сложные методы существуют для более сложных проблем. :-)

источник

2015-01-27 16:30:22 btilly

Настоящая теорема действительно не применима. Повторение имеет неправильную форму. – templatetypedef

Рекуррентное отношение для гипотетической рекурсивной функции

ответ

Смежные вопросы