У меня есть аргумент с моим другом, вчера у нас был экзамен. Я сказал, что не может, он сказал, что это будет случай 1. Вероятно, он прав, но я не могу понять, почему. Спасибо заранее.can t (n) = 2t (n/2) + n^0,5/logn может быть решена с использованием магистерской теоремы?
Для любого значения n, большего чем 1, n^(0,5/log n) имеет постоянное значение exp (0,5). Это может быть доказано, довольно легко:
x = n^(0.5/log n)
log(x) = (log n) * 0.5/(log n) = 0.5
=> x = exp(0.5) = 1.64872...
В результате второй срок вашего выражения можно рассматривать как константу. При постоянном втором члене ваша формула эквивалентна t(n) = 2t(n/2) + 1, которая имеет сложность O (n).
И да, твой друг прав. Это соответствует case 1, где значение c в f (n) ∈ O (n^c) равно нулю.
n^(0,5/log n) является константой (= exp (0,5)) для всех n! = 1 –
жаль, что я не понял, что вы написали. – Timur