2.3.2 Анализ времени работы алгоритмов «разделяй и властвуй»

Как оценить время работы рекурсивного алгоритма? При подсчёте требуется учитывать время, затрачиваемое на рекурсивные вызовы, так что получа­ется некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения.

Предположим, что алгоритм разбивает за­дачу размера п на а подзадач, каждая из которых имеет в b раз меньший размер. Будем считать, что разбиение требует времени D(n), а соединение полученных решений – времени С(п). Тогда получаем соотношение для времени работы Т(п) на задачах размера п (в худшем случае):

Т(п) = a·T(n / b) + D(n) + С(п).

Это соотношение выполнено для достаточно больших n, когда задачу имеет смысл разбивать на подзадачи. Для малых n, когда такое разбиение невозможно или не нужно, применяется один из прямых методов решения задачи. Поскольку n огра­ничено, время работы тоже не превосходит некоторой константы.