Рекуррентные отношения в структурах данных

Question

В классе Data Structures мы рассматриваем такие рекуррентные отношения, как T (n) и большие O-задачи O (n). Я был бы признателен за любые ресурсы для их изучения, мой учебник не охватывает T (n), и профессор пропускает много шагов.

Я не видел хорошего пошагового метода решения этих проблем. Я понимаю, что каждая проблема уникальна, но для этого должна быть какая-то структура.

Спасибо.

Answer 1

Проверьте Concrete Mathematics - A Foundation for Computer Science, это блестящая книга с большим количеством примеров и упражнений.

Answer 2

Другая замечательная книга Introduction to Algorithms. В нем есть довольно подробный раздел по решению рекуррентных отношений.

Вы правы, существует обобщенный метод решения простых рекуррентных отношений, называемый Master Theorem. (Объяснение в Введение в алгоритмы намного лучше, чем на странице Википедии.) Это не работает для каждого случая, но оно решает множество общих.