Решение сложного рекуррентного отношения для Traveling Salesman

Question

Мне нужно решить точную сложность времени для версии грубой силы Traveling Salesman с использованием отношения повторения.

Я разработал рекуррентное соотношение будет следующим: Т (п) = Т (п-1) * (п-1) +1

Но у меня возникают проблемы восстановитель, что это к замкнутой форме функции и, таким образом, получить точную временную сложность. Не из-за отсутствия попыток. Похоже, что это выходит как биномиальная последовательность, но моя алгебра немного ржавая.

Если бы кто-нибудь мог мне помочь или указать на правильный путь, я был бы признателен.

Спасибо!

Answer 1

Вот несколько советов:

• определить R (п) = Т (п)/(п-1)!
• решить для повторения R (п)
• выразить Т (п) в виде функции R (п)