c++ - 递归函数的渐近时间复杂度

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

立方米 = 立方米 = 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 & m3 无关紧要，因为它们在递归调用之外

a1 + m1*_ = 1 个时间单位(加法)

m1*_ = 1 个时间单位(乘法)

将 2 个递归调用加在一起是 1 个时间单位

m3*_ = 1 个时间单位(乘法)

根据我们给出的说明，每次都将使用相同的 # 调用两个递归函数，并且递归函数调用的每个连续数字都将小于最后一个，因为 d1 = d2 > 1。

所以 ARG 越大(与 n1 相比)，达到基本情况所需的时间越长，结果也越大。那么该算法需要 O(ARG) 时间？

如果有人能让我知道我是否在正确的轨道上，我将不胜感激。谢谢

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)

一旦你找到 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