Этот вопрос пришел в экзамен, и я не знаю, как это сделать, может кто-нибудь мне помочь или дать какой-то намек. Я думаю, что метод мастера здесь не применим? Пожалуйста, помогите.Как решить ниже рекуррентное отношение?
Т (п) = Т (п/2) + θ (LOGN)
Предполагая, что n является степенью 2, скажем n = 2^k, и для простоты, скажем T(n) = T(n/2) + lg(n), где lg является логарифм основание 2, и T(1) = lg(1) = 0.
T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1)
= lg(2^k) + lg(2^{k-1}) + ... + lg(2^0)
= k.lg(2) + (k-1)lg(2) + ... + 0.lg(2)
= (k + (k-1) + ... + 0) lg(2)
= k(k+1)/2
= lg(n)(lg(n)+1)/2
= Theta(lg(n)^2).
Для n не сил 2, можно отметить, что T является возрастающей функцией, и поэтому T(2^k) <= T(n) <= T(2^{k+1}) где k = floor(lg(n)). Из точного результата выше, мы получаем
k(k+1)/2 <= T(n) <= (k+1)(k+2)/2
и так
T(n) = Theta(floor(lg(n))^2) = Theta(lg(n)^2)
Вы можете иметь грубую верхнюю границу, отметив Theta (срубы п) O (журнал N), который является O (п). Полученная форма действительно поддается теореме Мастера. –