2

我被要求开发一个递归函数，然后分析渐近时间复杂度。

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

   }

}

我已经针对讲师的程序测试了我的递归函数，它的工作原理完全相同，所以我继续进行分析，但我遇到了困难。

我正在努力解决这个问题，所以请耐心等待。

我尝试部分解决方案：

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) 时间？

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

4

2 回答 2

3

递归调用是：

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

于 2013-09-30T16:25:08.160 回答
0

请注意，在每个递归级别上，您都会调用该函数两次。因此，从第一次调用c1开始，它会调用自己两次：c21和c22，然后从每个调用中它再次调用自己两次：c211、和c212，等等。在每个递归级别，您还有两次调用。在第 N 级，您将有 2^n 次调用，因此它是指数复杂度。c221c222

编辑：对不起，我的错。我没有注意到那里的论点存在分歧。在那种情况下，不会有 N 个级别，只有 log d (N)，其余的就像 Tony 写的那样。

于 2013-09-30T04:01:42.520 回答