Мастер Теорема применимо здесь?

Question

Пусть $ t (n):=begin {face} \ frac {2+ \ log n} {1+ \ text {log} n} t (\ lfloor \ frac {n} {2} \ Rfloor) + \ log ((n!) ^ {\ Log n}) & \ text {Если} n> 1 \\ 1 & \ Text {Если} n= 1 \ end {Cass} $

Мне нужно доказать, что $ t (n) \ in o (n²) $ , таким образом, $ t (n ) \ leq c \ cdot n² $

Я задавал вопрос здесь и я Иметь действительно большую помощь в прошлый раз, вещь после того, как мне было показано в прошлый раз, когда $ f (n)=log (n) \ cdot \ log (n!) $ Это $ \ theta (2 \ cdot \ log (n) \ cdot n)=theta (\ log (n) \ cdot n) $ Я думал, что могу Затем используйте основную теорему

Однако, поскольку $ a=frac {2+ \ log n} {1+ \ log n} $ не является константой, я не могу использовать основную теорему Но я подумал, что могу использовать верхнюю границу для $ a $ , поскольку $ \ frac {2+ \ log n} {1+ \ log n} <2 \ Quad \ forall n $ а затем используйте основную теорему для $ a= 2 $ , $ B= 2 $ . Но мне позволило использовать основную теорему после нахождения верхней границы для не постоянного $ a $ ?

Что бы другие способы показать, что $ t (n)= O (n ^ 2) $ ?

Answer 1

Да, вы можете определить $ t '(n)= 2 t' (\ frac {n} {2}) + \ theta (n \ log n) $ , Обратите внимание, что $ t (n) \ let '(n) $ и используйте основную теорему на $T '$ Для получения верхней границы $ O (n \ log ^ 2 n) $ на $T $ .

Поскольку для $ n \ Ge 2 $ , $ \ frac {2+ \ log n} {1+ \log n} \ le \ frac {3} {2} $ Вы можете получить лучшую верхнюю границу, сравнивая $ t $ $$ t ''=begin {Cass} \ frac {3} {2} t '' (\ frac {n} {2}) + \ theta (n \ log n) & \ Text {Если $ n \ ge2 $} \\ \ theta (1) & \ text {в противном случае} \ end {face}. $$ Применение основной теоремы на $ o (n \ log n) $ для $ T $ .

Answer 2

Да, вам разрешено использовать теорему магистра на верхних границах.

формально, просто определите s (n) в качестве функции, которая имеет верхние границы (какие рекурсивные вызовы на сам ) и используют теорему магистра на s (n).Вы знаете, что S (N) является обязательным для t (n) (вы можете доказать это в индукции, если вы действительно хотите) и, таким образом, если вам удалось показать, что S (N)= O (N ² ) Тогда также t (n)= o (n ^{2 )}

Лично, я никогда не объяснил, почему можно также использовать теорему магистра на верхних пределах, и я никогда не видел, чтобы кто-то пытался на самом деле объяснить это раньше (так как вы видели из объяснения, причина довольно просто) .

Я надеюсь, что мне удалось помочь: P