Как определять сложность у рекурсивных алгоритмов?
#include <iostream>
using namespace std;
int no_zeroes(int a, int b) {
if (a > b + 1) {
return 0;
}
if (a == 0 || b == 0) {
return 1;
}
return no_zeroes(a, b - 1) + no_zeroes(a - 1, b - 1);
}
int main()
{
setlocale(LC_ALL, "Russian");
int a, b;
cout << "Введите количество нулей: ";
cin >> a;
cout << "Введите количество единиц: ";
cin >> b;
cout << "Ответ: " << no_zeroes(a, b);
return 0;
}
Каким образом нужно определять сложность у рекурсивных алгоритмов? Что-то подсказывает, что сложность в худшем случае 2^(a + b), но как это можно сделать строже?
Ответы (3 шт):
В худшем случае когда сложность алгоритма будет a = bO(2^max(a,b)), так как каждый вызов функции делает два рекурсивных вызова, пока один из аргументов не достигнет нуля.
В координатах a-b выполняя дочерний вызов, мы суть сдвигаемся в одном из двух направлений:
Т.е., пренебрегая неоднородностью около начала координат, задача сводится к вычислению числа маршрутов, по которым можно добраться из заданной точки, в точку (a=0, b=-1), двигаясь только по разрешенным направлениям. Очевидно, мы должны сделать (b+1-a) шагов вниз, и a шагов по диагонали, вопрос только в очередности этих шагов. Таким образом, ответ: (b+1)! / a! / (b-a+1)!
Пренебрегая первый множителем в формуле Стирлинга, получим:
O((b+1)! / a! / (b-a+1)!) = O( (b/(b-a+1))^(b-a+1) * (b/a)^a )
Худшим a для заданного b, очевидно, является a=b/2. Оставляя зависимость от одного параметра b, получим O(2^b), однако, так предоставлять не стоит, поскольку в случае если пользователя интересует рост сложность, "в заданном направлении" на плоскости a-b, эта формула может существенно завысить сложность. Если нужно избавиться от знаменателей, я бы советовал использовать: O( min( (b-a)^a, a^(b-a), 2^b ) ), по крайней, мере она правильно описывает окрестности границ: a<<b, (b-a)<<b .
Выписать функцию сложности в виде рекуррентного соотношения.
-
- (а) Прочитать Конкретную математику Кнута, Грехэма, Поташника, научиться работать с производящими функциями, вывести формулу для функции сложности ...
- (б) ... или понять что решение связано с биномиальными коэффициентами. А для них решения выводятся из линейности - не надо читать толстые книги.
Доказать что найденная функция отвечает всем требованиям из первого пункта.
NB В этом ответе выведена точная формула для времени работы. Этого обычно не нужно (О-большое), но тут повезло.
NB Универсального способа оценить сложность любого алгоритма не существует. Потому что тогда появится решение для проблемы остановки, а этого не может быть никогда. Оценка сложности всегда будет сложной. :)
Обозначения (первый пункт программы)
Обозначим f(a, b) - время вычисления no_zeroes(a, b). Тогда f обладает следующими свойствами:
- f(a, b) = 1 если a > b + 1 (первое условие);
- f(a, b) = 1 если a = 0 или b = 0 (второе условие);
- f(a, b) = 1 + f(a, b - 1) + f(a - 1, b - 1) (рекурсивная ветка).
Не запутайтесь: f похожа по свойствам на no_zeros но они не равны. Тело no_zeros исполняется за константу, если исключить рекурсивные вызовы. Эта константа в формулах выше замена на единицу - O-большое разрешает. Иначе говоря f(a, b) - число рекурсивных вызовов no_zeroes если та вызвана с аргументами a, b.
Введём обозначение (ba) - биномиальный коэффициент.
Формула (последний пункт программы)
Утверждение: если 0 ≤ a ≤ b + 2, то f(a, b) = 2[(ba) + (ba-1) + (ba-2)] - 1.
Доказательство:
Первое условие для f упрощается до a = b + 2. Тогда
f(a, b) = f(b + 2, b) = 2[(bb+2) + (bb+1) + (bb)] - 1 = 2[0 + 0 + 1] - 1 = 1
Второе условие, часть a = 0. Тогда
f(a, b) = f(0, b) = 2[(b0) + (b-1) + (b-2)] - 1 = 2[1 + 0 + 0] - 1 = 1
Второе условие, часть b = 0 превращается в b = 0 и 0 ≤ a ≤ 2. Тогда одно из слагаемых в квадратных скобках - единица, остальные два - нули:
f(a, b) = f(a, 0) = 2[(0a) + (0a-1) + (0a-2)] - 1 = 2[1] - 1 = 1
Рекурсивная ветка: b > 0, 0 < a ≤ b + 1. Тогда
f(a, b) = 2[(ba) + (ba-1) + (ba-2)] - 1 =
= 2[((b-1a)+(b-1a-1)) + ((b-1a-1)+(b-1a-2)) + ((b-1a-2)+(b-1a-3))] - 1 =
= 2[(b-1a) + (b-1a-1) + (b-1a-2)] + 2[(b-1a-1) + (b-1a-2) + (b-1a-3)] - 1 =
= 1 + [2[(b-1a) + (b-1a-1) + (b-1a-2)] - 1] + [2[(b-1a-1) + (b-1a-2) + (b-1a-3)] - 1] =
= 1 + f(a, b - 1) + f(a - 1, b - 1)
Доказано.
Выводы
f(a, b) = 2[(ba) + (ba-1) + (ba-2)] - 1 достигает максимума если 2(a-1) ≈ b. В википедии есть оценки из которых выводится f(a, b) = O(2b/√(πb/2)).
Как догадаться до формулы (пункт 2(б))
Рекурсивная часть no_zeros повторяет рекуррентную формулу для биномиальных коэффициентов. Сравните:
no_zeros(a, b) = no_zeros(a, b - 1) + no_zeros(a - 1, b - 1)(ba) = (b-1a) + (b-1a-1)
Это всегда означает что функция вычисляет какую-то линейную комбинацию биномиальных коэффициентов. В нашем случае no_zeros(a, b) = (b-1a). Догадаться можно посмотрев таблицу значений no_zeros. Каждый кто видел треугольник Паскаля его уже не забывает никогда:
b 6 1 7 21 35 35 21 7 1 0 ... 5 1 6 15 20 15 6 1 0 ... 4 1 5 10 10 5 1 0 ... 3 1 4 6 4 1 0 ... 2 1 3 3 1 0 ... 1 1 2 1 0 ... 0 1 1 0 ... 0 1 2 3 4 5 6 7 8 a
Но это таблица для no_zeros, а нам нужна для f. У f другая рекуррентная формула, другая таблица - там труднее увидеть биномиальные коэффициенты. Поэтому отвлечёмся на минуту.
Давайте на минуту представим что no_zeros возвращает не числа, а формулы для их вычисления. Например:
no_zeros(2, 2) = no_zeros(1, 2) + no_zeros(1, 1) = = (no_zeros(0, 2) + no_zeros(0, 1)) + (no_zeros(0, 1) + no_zeros(0, 0)) = = (0 + 1) + (1 + 1) = 0 + 1 + 1 + 1
Число знаков в последней сумме (пробелы отбрасываем) совпадает со сложностью вычисления no_zeros: 0 - первое условие, 1 - второе условие, + - рекурсивный вызов.
Следите за руками: если бы в формуле не было нулей, то число плюсов было бы на единицу меньше числа единиц. А число единиц равно результату no_zeros. Следовательно, сложность вычисления была бы (b-1a) + (b-1a) - 1. Сложность функции пропорциональна значению функции потому что мы складываем единицы!
Нули всё портят. Можно доказать что их доля мала (не велика), но...
Вернёмся к f(a, b). Таблица значений:
b 6 1 13 43 81 99 81 43 13 1 ... 5 1 11 31 49 49 31 11 1 ... 4 1 9 21 27 21 9 1 ... 3 1 7 13 13 7 1 ... 2 1 5 7 5 1 ... 1 1 3 3 1 ... 0 1 1 1 ... 0 1 2 3 4 5 6 7 8 a
В каждом ряду центральная симметрия. Значения образуют треугольник обрамлённый единицами. Он похож на треугольник Паскаля.
Из формулы f(a, b) = 1 + f(a, b - 1) + f(a - 1, b - 1) уберём единицу заменой g(a, b) = f(a, b) + 1:
(g(a, b) - 1) = 1 + (g(a, b - 1) - 1) + (g(a - 1, b - 1) - 1)
g(a, b) = g(a, b - 1) + g(a - 1, b - 1)
Таблица значений g(a, b):
b 6 2 14 44 82100 82 44 14 2 ... 5 2 12 32 50 50 32 12 2 ... 4 2 10 22 28 22 10 2 ... 3 2 8 14 14 8 2 ... 2 2 6 8 6 2 ... 1 2 4 4 2 ... 0 2 2 2 ... 0 1 2 3 4 5 6 7 8 a
Все значения чётные. Делим на два: h(a, b) = g(a, b) / 2. Таблица:
b 6 1 7 22 41 50 41 22 7 1 ... 5 1 6 16 25 25 16 6 1 ... 4 1 5 11 14 11 5 1 ... 3 1 4 7 7 4 1 ... 2 1 3 4 3 1 ... 1 1 2 2 1 ... 0 1 1 1 ... 0 1 2 3 4 5 6 7 8 a
Последнюю таблицу можно расписать как сумму трёх таблиц:
b 6 1 6 15 20 15 6 1 0 ... 0 1 6 15 20 15 6 1 0 ... 0 0 1 6 15 20 15 6 1 0 5 1 5 10 10 5 1 0 ... 0 1 5 10 10 5 1 0 ... 0 0 1 5 10 10 5 1 0 .. 4 1 4 6 4 1 0 ... 0 1 4 6 4 1 0 ... 0 0 1 4 6 4 1 0 ... 3 1 3 3 1 0 ... + 0 1 3 3 1 0 ... + 0 0 1 3 3 1 0 ... 2 1 2 1 0 ... 0 1 2 1 0 ... 0 0 1 2 1 0 ... 1 1 1 0 ... 0 1 1 0 ... 0 0 1 1 0 ... 0 1 0 ... 0 1 0 ... 0 0 1 0 ... 0 1 2 3 4 5 6 7 8 a 0 1 2 3 4 5 6 7 8 a 0 1 2 3 4 5 6 7 8 a
Это три треугольника Паскаля: первый нормальный, второй смещён вправо на столбец, третий - на два столбца. Следовательно h(a, b) = (ba) + (ba-1) + (ba-2).
В действительности таблицы рисовать не нужно. Достаточно соотношения для h (даже для g) и трёх единиц (для g двоек) в нулевой строке. Из каждой единицы растёт свой треугольник Паскаля, которые складываются в силу линейности рекуррентной формулы.
Теперь проходим всю цепочку назад, пишем формулу для f(a, b), пишем начальные значения, доказываем, пишем ответ.