Как решить T (n) = T (n / 4) + T (3n / 4) + nlogn

Question

У меня есть вопрос решения этой рекурсивной сложности T(n)=T(n/4)+T(3n/4)+nlogn. Вы можете помочь мне решить это?

Answer 1

Вы можете использовать метод Акра-Бацци со следующими параметрами:

a_1 = a_2 = 1, 
b_1 = 1/4, b_2 = 3/4
p = 1

T(n) = \Theta(n * (1 + integral( u log(u)/ u^2 du,1, n))) = 
       \Theta(n * (1 + (log^2(n)/2))) = 
       \Theta(n log^2(n))

Answer 2

Обратите внимание, что 3n / 4> n / 4. Отсюда видно, что T (n) <= 2T (3n / 4) + n log n. </p>

Теперь мы можем применить основную теорему. Мы можем видеть, что a = 2, b = 4/3 и f (n) = n log n

Мы можем видеть, что log_ (4/3) 2 = 2,41

Следовательно, n ^ log_b a> = f (n).

Таким образом, по теореме Магистра T (n) = O (n ^ 2.41)