Рецидив: Т (п) = 3T (п/2) + п^2 (ЛГН)

Question

Вот полный вопрос ...

Анализ повторяемости деревьев. Найдите хорошую нерекурсивную функцию f (n) такую, что T (n) = Θ (f (n)). Покажите свою работу: каково количество уровней, количество экземпляров на каждом уровне, работа каждого экземпляра и общая работа на этом уровне.

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

а) Т (п) = 3T (п/2) + п^2 (ЛГН)

Я действительно понятия не имею, с чего начать.

Answer 1

Этих типов рецидивов решаются с Master's theorem

В вашем случае a=3, b=2 и поэтому c = log2(3) < 2.

Таким образом, вы в третьем случае и ваша сложность мастер теорема O(n^2 * log(n))