Решение отношения повторения без итерации

Как мне это решить?

T(n) = T(n/4) + T(3n/4) + cn

Ответ - \ theta (nLogn)

Как этот ответ может быть получен с помощью основной теоремы или любого другого эффективного метода?


recursion recurrence time-complexity big-theta
person Rohit Roy    schedule 13.10.2016    source источник
comment
Да, есть. Герерирующие функции. Это слишком широко для Stack Overflow. Погуглите это в Википедии. Это довольно хорошее вступление к теме.   -  person xenteros    schedule 13.10.2016
comment
Можем ли мы использовать здесь основную теорему?   -  person Rohit Roy    schedule 13.10.2016
comment
@RohitRoy Нет, здесь нельзя использовать основную теорему, здесь лучше использовать дерево рекурсии.   -  person Sumeet    schedule 13.10.2016

Ответы (1)


arrow_upward
2
arrow_downward

Дерево рекурсии для данной рекурсии будет выглядеть так:

                                Size                        Cost

                                 n                           n
                               /   \
                             n/4   3n/4                      n
                           /   \     /    \
                        n/16  3n/16 3n/16  9n/16             n

                        and so on till size of input becomes 1

Длинный простой путь от корня до листа будет n-> 3n / 4 -> (3/4) ^ 2 n .. до 1

 Therefore  let us assume the height of tree = k

            ((3/4) ^ k )*n = 1 meaning  k = log to the base 4/3 of n

 In worst case we expect that every level gives a cost of  n and hence 

        Total Cost = n * (log to the base 4/3 of n)

 However we must keep one thing in mind that ,our tree is not complete and therefore

 some levels near the bottom would be partially complete.

 But in asymptotic analysis we ignore such intricate details.

 Hence in worst Case Cost = n * (log to the base 4/3 of n)

          which  is O( n * log n )

Теперь давайте проверим это с помощью метода подстановки:

 T(n) =  O( n * log n)  iff T(n) < = dnlog(n) for some d>0

 Assuming this to be true:

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

      <= d(n/4)log(n/4) + d(3n/4)log(3n/4) + n

       = d*n/4(log n  - log 4 )  + d*3n/4(log n  - log 4/3) + n

       = dnlog n  - d(n/4)log 4 - d(3n/4)log 4/3  + n

       = dnlog n  - dn( 1/4(log 4)  -  3/4(log 4/3)) + n

       <= dnlog n

       as long as d >=  1/( 1/4(log 4)  -  3/4(log 4/3) )
person Sumeet    schedule 13.10.2016
comment
Хорошее объяснение, но почему мы не можем использовать здесь master? предложение можно переписать как T (n) = 2T (3n / 4) + cn в случае наихудшей временной сложности. И тогда мы можем использовать мастер - person Mohit Kumar; 13.10.2016
comment
@MohitKumar Как вы измените рецидив любого из трех случаев? Вот почему. - person Sumeet; 13.10.2016
comment
это может быть не так - person Rohit Roy; 13.10.2016