Нахождение рекурсивной функции и математического выражения из заданного кода - PullRequest
Новая
       3

Нахождение рекурсивной функции и математического выражения из заданного кода

1 голос
/ 05 февраля 2020

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

Код: 

int M(int B[],int l,int r)
{
    if(l == r) return (B[l]>0)?B[l]:0;
    int m = (l+r)/2;
    int mls = M(B,l,m);
    int mrs = M(B,m+1,r);
    int mlbs = 0, lbs = 0;
    for(int i = m;i >= l;i--){
        lbs += B[i]; 
        if(lbs > mlbs) mlbs = lbs;
    }
    int mrbs = 0, rbs =0;
    for(int j = m+1;j <= r;j++){   
        rbs += B[j];                 
        if(rbs > mrbs) mrbs = rbs;
    }                              
    return Max3(mls,mrs,mlbs+mrbs);
}

Вопрос: 

Then find
(a) Math expression of the code
(b) Recurrence Function of the code
(c) Time complexity of the code using one of the methods discussed. (I have learn master theorem, recurrence tree, and subtitution)

До сих пор я проанализировал операцию с кодом ниже 

// T(n)
int M(int B[],int l,int r)
{
    if(l == r) return (B[l]>0)?B[l]:0;     // 1, because the comparation in the return
                                           //    will be rarely occur
    int m = (l+r)/2;                       // 3
    int mls = M(B,l,m);                    // T(n / 2) \
                                           //           -> 2T(n/2)
    int mrs = M(B,m+1,r);                  // T(n / 2) /
    int mlbs = 0, lbs = 0;                 // 2
    for(int i = m;i >= l;i--){             // loop -> n / 2
        lbs += B[i];                       //   1
        if(lbs > mlbs) mlbs = lbs;         //   1, if the element on the B is negative, then it
                                           //      produce a random pattern so we can ignore it
    }                                      // end loop
    int mrbs = 0, rbs =0;                  // 2
    for(int j = m+1;j <= r;j++){           // loop -> n / 2
        rbs += B[j];                       //   1
        if(rbs > mrbs) mrbs = rbs;         //   1, if the element on the B is negative, then it
                                           //      produce a random pattern so we can ignore it
    }                                      // end loop
    return Max3(mls,mrs,mlbs+mrbs);        // 3, Max3 would be O(2)
}

Функция будет 

T(n) = 1 + 3 + T(n/2) + T(n/2) + 2 + 2 * (n/2) + 2 + (n/2) * (2 + 1) + 2 + 2 * (n/2) + 2 + (n/2) * (2 + 1) + 3
Then,
T(n) = 2 * T(n/2) + 3n + 15

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

Мой вопрос

Правильно ли я делаю это, если у меня неверно и если возможно, объясните проблему? И как я могу получить функцию повторения или математическое выражение (я все еще путаю различать guish оба)?

...