Как анализировать временную сложность рекурсивных алгоритмов?

План ответа

1. Привести формальное определение понятия рекуррентного соотношения для временной сложности рекурсивного алгоритма
2. Перечислить методы решения рекуррентных соотношений (метод подстановки, метод рекуррентных деревьев, метод биномиальных коэффициентов и др.)
3. Привести пример анализа временной сложности рекурсивного алгоритма с использованием одного из методов решения рекуррентных соотношений

Ответ на 1 минуту

Временная сложность рекурсивных алгоритмов анализируется с помощью рекуррентных соотношений. Например, алгоритм быстрой сортировки имеет рекуррентное соотношение T(n) = 2T(n/2) + O(n), которое решается методом рекуррентных деревьев. Его сложность — O(n log n).