Преобразование рекурсии в динамическую и вычисление ее временной сложности

Я решаю код, и моя функция рекурсии получила что-то вроде этого->

int rec(n)
{

  if(n>=(n/2+n/3+n/4))
  {
      return n;
  }


  else
  {

     return  rec(n/2) + rec(n/3) + rec(n/4); 

  }

}

Мне было интересно, какова будет временная сложность этой функции?

Я думаю, что рекуррентное отношение было бы-

T(n) = T(n/2) + T(n/3) + T(n/4) + f(n)

Как решить это рекуррентное соотношение? Каким было бы значение f (n) в этом случае?

Также как преобразовать это в динамическое программирование?

Код, который я написал для преобразования этого в динамический, -

    long long  rec(long long n)
{
    long long c[n]; // The number range is between 1 to 10^9


    for(int i=0;i<n;i++)
    c[n]=0;


    if(n>=(n/2+n/3+n/4))
    {
        c[n]=n;
        return n;
    }
    else
    {
        if (c[n]==0)
        c[n]=c[n/2]+c[n/3]+c[n/4];
        return c[n];
    }

}

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

Спасибо


recursion recurrence time-complexity dynamic-programming
person Piyush    schedule 30.04.2013    source источник
comment
Практическое правило: Теорема Мастера. Это O(n ^ (a / b)), я. е. полиномиальный.   -  person    schedule 30.04.2013
comment
Ни одна из этих функций не использует отступы последовательно, и из-за непоследовательного отступа их довольно легко неправильно прочитать. Я отказываюсь читать такое бельмо на глазу. Возгордитесь и исправьте отступы. Надеюсь, другие последуют моему примеру.   -  person autistic    schedule 30.04.2013
comment
Второй фрагмент кода не компилируется и имеет очевидные ошибки из-за отсутствия фигурных скобок. Пожалуйста, дайте нам реальный код, который вы запустили, чтобы мы могли дать содержательный отзыв.   -  person templatetypedef    schedule 30.04.2013
comment
Хорошо, что в опубликованный вопрос внесены необходимые изменения.   -  person Piyush    schedule 01.05.2013

Ответы (1)


arrow_upward
1
arrow_downward

If (n> = (n / 2 + n / 3 + n / 4)) в основном эквивалентно if (n ‹= 0). n не может быть меньше 0, поэтому можно написать if (n == 0) return n; Это означает, что временная сложность определяется следующим рекуррентным уравнением:

T(0) = 1
T(n) = T(n/2) + T(n/3) + T(n/4)

Поскольку разделение задачи на более мелкие задачи не является симметричным (и поскольку n / 2 + n / 3 + n / 4 = 13n / 12, что больше, чем n) в первом приближении (большом), я бы сказал, что между O (nlogn) и O (n ^ 2). Я пытался доказать, что это O (nlog2n), но не проверял (под log2n я имею в виду журнал по базе 2 из n):

T(n) <= cnlog2n

с этого момента я буду писать просто логн

T(n) <= cn/2*logn/2 + cn/3*logn/3 + cn/4*logn/4
      = cn/2*logn - cn/2*log2 + cn/3*logn - cn/3*log3 + cn/4*logn - cn/4*log4
      = cn/2*logn - cn/2 + cn/3*logn - cn/3*log3 + cn/4*logn - cn/2
      = 13/12*cn*logn - cn(log3/3 - 1)

что не меньше или равно cnlogn

O (n ^ 2) можно доказать следующим образом:

if T(n) = O(n^2) then T(n) <= cn^2
T(n) <= c(n/2)^2 + c(n/3)^2 + c(n/4)^2
      = cn^2/4 + cn^2/9 + cn^2/16
      = 15cn^2/36 <= cn^2

поэтому гипотеза O (n ^ 2) верна, однако она может быть не очень точной. Вы можете попробовать другую гипотезу между O (nlogn) и O (n ^ 2) и посмотреть, верны ли они, как я сделал выше.

person red_eyes    schedule 03.05.2013