2017-02-22 38 views
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?

+1

Нет, полиномы имеют постоянные целые показатели, показатель экспоненты является переменным. – LutzL

+0

Итак, мы можем решить этот вопрос с помощью мастеров Metthod, если да, то в этом случае? –

+1

Нет, вы не можете. Но вы получаете '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

ответ

1

Это не только не многочлен, но и хуже, чем факт. O (n^n) доминирует над O (n!). Также в методе мастеров f (n) должен быть многочлен, поэтому вы не можете его использовать.

Смежные вопросы