Выписать функцию сложности в виде рекуррентного соотношения.
-
- (а) Прочитать Конкретную математику Кнута, Грехэма, Поташника, научиться работать с производящими функциями, вывести формулу для функции сложности ...
- (б) ... или понять что решение связано с биномиальными коэффициентами. А для них решения выводятся из линейности - не надо читать толстые книги.
Доказать что найденная функция отвечает всем требованиям из первого пункта.
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) = (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), пишем начальные значения, доказываем, пишем ответ.
