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

Question

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

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

Спасибо.

Answer 1

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

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

Answer 2

Проверка Конкретная математика - основа компьютерных наук , это блестящая книга с множеством примеров и упражнений.