Найти время выполнения нескольких рекуррентных используя итерационную Замена

Question

Я пытаюсь найти время выполнения следующего повторения с использованием итеративной подстановки:

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

Вопрос заключается в том, что существует два T(n/x) условия и найти общую форму для этого случая имеет оказалось довольно сложной задачей. Есть ли общая рекомендация, которой следует следовать, используя итеративную замену для таких случаев?

Answer 1

Этот рецидив относится к классу Akra–Bazzi повторяющимся. После формулы раствор:

Кроме того, предположим, что T(1) = c0 то вы можете доказать, что T(n) <= max(6,c0)*n по индукции.

Вы также можете использовать правило замещения. Вот как:

T(n) = T(n/2)+T(n/3) + n = 
= n+(n/2+n/3)+T(n/(2*2))+T(n/(2*3))+T(n/(3*2))+T(n/(3*3)) 
= n+(n/2+n/3)+(n/(2*2)+n/(2*3)+n/(3*2)+n/(3*3)) 
      +T(n/(2*2*2))+T(n/(2*2*3)) 
      +T(n/(2*3*2))+T(n/(2*3*3)) 
      +T(n/(3*2*2))+T(n/(3*2*3)) 
      +T(n/(3*3*2))+T(n/(3*3*3))= 
... 
= n * (1 + 5/6 + (5/6)^2 + (5/6)^3 + (5/6)^4 + ...) 
= 6 * n (assuming n = 2^k3^k. you get < 6*n otherwise) 

Answer 2

Ничего формального здесь, но

T(n) = 2T(n/2) + n // O(nlog(n)) 

Так что ваш рецидив может все еще быть O (Nlog (п))?

И что такое базовый корпус?