Метод замещения

Question

Я просто хотел проверить некоторые вещи, сделал ли я шаги, описанные ниже, верно?

T(n)   = 3T(n/3) + n  : Theta(nlogn)

O(nlogn)

T(k)   = cklog(k)  k<n

T(n/4) = c(n/3)log(n/3)
       = c(n/3)[logn - log3]
       = c(n/3)logn - c(n/3)log3    

T(n)   = cnlogn-cnlog3 + n

       <= cnlogn -cn + n 
       <= cnlogn -dn **[STEP A]**
       <= cnlogn if c >= d

Omega(nlogn)
   >= cnlogn -cn + n 
   >= cnlogn -dn **[STEP A]**
   >= cnlogn if 0 < c <= d  

У меня проблемы с шагом A, в результате чего я получил диапазон c:

c> = 1 для верхней границы 0

Есть ли особая причина, по которой вы бы объединили cn + n.Я могу видеть логику, но стоит ли делать этот шаг?Потому что тогда я могу сделать это для любого случая ... что немного странно ..

Answer 1

Вы были все еще правы до:

T(n) = cnlogn-cnlog3 + n
     >= cnlogn -cn + n

для Ω(nlogn)

, поскольку оно справедливо только для c <= 0, что противоречит нашему предположению, что c> = 0.

Один из способов исправить второе доказательство может быть:

T(n) = cnlogn - cnlog3 + n
     = cnlogn - n(clog3 - 1)
     <= cnlogn when c >= 1/log3 

Следовательно: T(n) = Ω(nlogn).

В общем, значения нижней и верхней границ не имеют большого значения. Цель состоит в том, чтобы найти две константы c1 и c2 такие, что:

c1*n*logn <= T(n) <= c2*n*logn forall n >= some n0.