0
Is n к власти n (i-e n^n) полином? Можно ли решить T(n) = 2T(n/2) + n^n с использованием мастер-метода?N power n i-e n^n полиномиальна или нет? Существует ли какая-либо полиномиальная разность между n^2 и n^n?
Нет, полиномы имеют постоянные целые показатели, показатель экспоненты является переменным. – LutzL
Итак, мы можем решить этот вопрос с помощью мастеров Metthod, если да, то в этом случае? –
Нет, вы не можете. Но вы получаете 'T (n)/n = T (n/2)/(n/2) + n^(n-1)', который может быть легко повторен, а 'n^(n-1)' явно доминирует над (n/2), (n/4)^(n/4-1) 'в сумме, так что в худшем случае вы получите« T (n) = O (log (n) * n^n) 'и с некоторыми лучшими аргументами, возможно, также« T (n) = O (n^n) ». – LutzL