Основная теорема о рекурсии

Алла: А вон на горизонте и долгожданный Удотинск!

Рита: Наконец-то, я еле иду...

Гоша: Классно время провели! Теперь я точно специалист по рекурсии! Да ведь, Тимофей?

Тимофей: Ну, неплохо бы тебе ещё знать основную теорему о рекурсии. Если уж хочешь себя рекурсивным профи называть!

Гоша: А что это? Я вообще обычно перевожу разговор на другую тему, когда слышу слово «теорема». Или просто ухожу, если есть возможность.

Тимофей: Эта теорема помогает оценить оценку сложности алгоритмов, реализованных рекурсивно. А то как понять, стоит ли использовать рекурсивную реализацию алгоритма, если не знаешь степень его эффективности?

Гоша: Тогда расскажи про теорему! Только, пожалуйста, без заумных слов и многоэтажных формул.

Тимофей: Допустим, изначально объём задачи (то есть размер входных данных) n. Обозначим количество подзадач, на которые разбивается задача, за a. Пусть размер каждой подзадачи уменьшается в b раз и становится равным целой части сверху от n/b. А сложность консолидации после решения подзадач - О - большое от n в степени d.

Тогда

Первое слагаемое значит, что мы a раз решаем задачу со сложностью, равной целой части сверху от n/b.

Второе — это затраты на консолидацию результатов меньших задач. Консолидация нужна не везде. Например, если используем алгоритм бинарного поиска, то каждый раз мы просто идём в одну из половинок массива. Что происходит с остальными его частями, неважно.

А вот если мы, к примеру, сортируем данные, разбивая массив на части, то результаты подзадач нужно объединить. На это требуется время. Но вернёмся к разговору о нём потом, а то мы уже почти пришли.

Суть теоремы вот в чём.

Пусть сложность задачи записывается формулой для T(n) для некоторых a > 0, b >1, d ≥ 0. Тогда:

Гоша: Ты же обещал без формул?!

Тимофей: Без многоэтажных. И не я обещал, а ты просил!

Продолжим рассматривать пример с бинарным поиском. В этом случае d = 0, так как затрат на консолидацию нет. Размер задачи уменьшается в два раза, то есть b = 2. Количество задач не меняется, то есть a = 1.

Получаем:

То есть T(n) = log(n).

То, что сложность бинарного поиска именно такая, ты знаешь.

Это лишь пример. В случае бинарного поиска оценить сложность легко и без теоремы. Но иногда она бывает действительно полезной! Сейчас уже нет времени, нас ждет Кондратий! Но как-нибудь я тебе расскажу про сортировки, и эта теорема пригодится.

Алла по дороге наслушалась историй про рекурсию и ночью ей снились разные рекурсивные алгоритмы.

Первый из них — алгоритм выбора наилучшего маникюрного салона. Он решался рекурсивно путём деления всего города четыре части. Количество подзадач — две, размер подзадачи уменьшается в два раза. Коэффициент консолидации равен трём.

Какая сложность у рекурсивного алгоритма?

O(nlogn)

Сложность этого алгоритма O(n³). Дано: 2 подзадачи, то есть а=2; размер каждой подзадачи уменьшается в 2 раза –– b=2; коэффициент консолидации 3 –– d=3. Подставим данные в формулу теоремы и получим d > log_b(a), то есть сложность O(n^d), что равно O(n³).

O(n³)

O(n²)

O(n)

O(n⁵)