Я хочу доказать, почему сложность детерминанта Лапласа или рекурсивного алгоритма равна n!. Может ли кто-нибудь доказать это для меня? Я не знаю, как тогда это могло быть n!, учитывая, что уравнение T(n)=nT(n-1)+3n-1 включает только умножение и сложение.
Доказательство сложности рекурсивного определителя
comment
Большой! У вас есть вопрос?
- person trincot schedule 23.10.2019
comment
Можете ли вы помочь мне с этим? Мое уравнение почти трудно ответить.
- person Havoc schedule 23.10.2019
comment
Что вы пробовали, что не работает с этим?
- person Willem Van Onsem schedule 23.10.2019
comment
Уравнение T (n) = nT (n-1) + 3n-1 с учетом множеств и плюсов. Как я могу решить это, потому что я не знаю, что делать с частью 3n-1.
- person Havoc schedule 23.10.2019
Ответы (1)
Попробуйте расширить:
T(n) = n T(n-1) + 3n-1 =
n ((n-1)T(n-2) + 3(n-1)-1) + 3n-1 =
n (n-1) T(n-2) + 3 n (n-1) - n + (3n - 1)
Теперь по индукции вы можете показать, что (если T(1) = 1):
T(n) = n (n-1) (n-2) ... 1 + 3(n + n (n-1) + ... + n!) -
(1 + n + n (n-1) + ... + n (n-1) ... n * (n-1) * ... * (n-2))
= Theta(n!)
person
OmG
schedule
23.10.2019
Я думаю, что ваше расширение неверно, в уравнении должно быть n ^ 2, потому что вы не можете убрать его из парезиса.
- person Havoc; 23.10.2019
@Havoc есть! в 1_. Однако это не меняет асимптотическую сложность.
- person OmG; 23.10.2019
Я думаю, я понял, почему, если вы напишете полное уравнение, последняя дополнительная часть будет что-то вроде n!(3n-(3n+1)) и останется n! .
- person Havoc; 23.10.2019
@Havoc насчет расширения, ты был прав! Ответ обновляется, но сложность не меняется.
- person OmG; 23.10.2019
