Асимптотическая временная сложность рекурсивной функции

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

f(N) = 0, if N < N1

f(N1) = C1

f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1

Мы должны предположить, что:

s1 = s2 = 0

м2 = м4 = 1

d1 = d2> 1

//the user enters N1 C1 A1 M1 M2 M3 M4 D1 D2 S1 S2 and then ARG

int Recursion_Plus(int ARG)
{

if (ARG < n1)
{
return 0;
}

else if(ARG == n1)
{
return c1;
}

else if(ARG > n1 )
{

return a1 + m1
*
Recursion_Plus(m2*ARG/d1 - s1)
+
m3*Recursion_Plus(m4*ARG/d2 - s2);

}

}

Я проверил свою рекурсивную функцию по программе инструктора, и она работает точно так же, поэтому я перешел к анализу, где столкнулся со стеной.

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

Моя попытка частичного решения:

2 сравнения (если ARG < N1 & если ARG == N1) займет 1 единицу времени

a1 & m1 & м3 незначительны, потому что они вне рекурсивного вызова

a1 + m1 *_ = 1 единица времени (дополнение)

m1 *_ = 1 единица времени (умножение)

сложение 2 рекурсивных вызовов вместе — это 1 единица времени

м3 *_ = 1 единица времени (умножение)

Из приведенных инструкций обе рекурсивные функции будут вызываться с использованием одного и того же # каждый раз, и каждый последующий номер, который вызывает рекурсивная функция, будет меньше последнего, потому что d1 = d2> 1.

Таким образом, чем больше ARG (по сравнению с n1), тем больше времени требуется для достижения базового варианта и тем больше будет результат. Таким образом, алгоритм занимает время O (ARG)?

Я был бы признателен, если бы кто-нибудь позволил мне познать меня, если я на правильном пути. Спасибо

2

Решение

рекурсивный вызов:

f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1

с

s1 = s2 = 0
m2 = m4 = 1
d1 = d2 > 1

у нас есть

f(N)= A1 + M1*f(N/D1) Op M3*f(N/D1), if N > N1

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

Итак, дело в том, чтобы найти T, например:

T(n)=2*T(n/D)

Как только вы найдете T (n), у вас будет номер вызова вашего Recursion_Plus, так как мы говорим об асимптотической сложности, не имеет значения беспокоиться о последних вызовах (т.е. n<N1).

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

Каждый вызов T вызывает 2 вызова T, но с # делением на D, затем 4 вызова с # делением на D ^ 2 …

сложность 2^(logD(n))logD(n)=ln(N)/ln(D) )

частный случай : with D=2, the complexity is n

3

Другие решения

Обратите внимание, что на каждом уровне рекурсии вы вызываете функцию дважды. Итак, с первого звонка c1 он вызывает себя дважды: c21 а также c22затем после каждого из этих вызовов он снова вызывает себя дважды: c211, c212, c221 а также c222и т. д. На каждом уровне рекурсии у вас в два раза больше звонков. На N-м уровне у вас будет 2 ^ n вызовов, так что это экспоненциальная сложность.

Редактировать: Извините, мой плохой. Я не заметил, что аргумент там разделен. В этом случае не будет N уровней, будет только логd(N), а остальное как Тони написал.

0