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

Question

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

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

m2 = m4 = 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); 

    } 

} 

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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) 

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

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

Каждый вызов Т индуцируют 2 вызовы Т, но с # разделите на D, то 4 вызова с # разделите на D^2 ...

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

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

Answer 2

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

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