Результаты анализа. Замечания

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

Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:

• алгоритм поиска элемента в неупорядоченном массиве не может иметь верхнюю оценку сложности лучше, чем O(n). Это связано с тем, что невозможно определить отсутствие элемента в массиве (худший случай) не просмотрев все его элементы;
• возможно формально доказать, что не возможен алгоритм сортировки произвольного массива, работающий лучше чем O(n⋅logn) [5].

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

Лекция 4 Простые рекурсии. Рекурсивное программирование задач

и рекурсивные функции (2 часа)

 

 План

 4.1 Простые рекурсии

 4.2 Рекурсия и итерация

Сложность рекурсивных вычислений.

 

Простые рекурсии

Рекурсия – фундаментальное понятие в математике и компьютерных науках. В языках программирования рекурсивной программой называется программа, которая обращается сама к себе (подобно тому, как в математике рекурсивная функция определяется через понятия самой этой функции). Рекурсивная программа не может вызывать себя до бесконечности, следовательно, вторая важная особенность рекурсивной программы – наличие условия завершения, позволяющее программе прекратить вызывать себя.

Таким образом рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей более простыми данными.

Как следствие, рекурсивная программа должна иметь как минимум два пути выполнения, один из которых предполагает рекурсивный вызов (случай «сложных» данных), а второй – без рекурсивного вызова (случай «простых» данных).

Примеры рекурсивных программ. В ряде случаев рекурсивную подпрограмму можно построить непосредственно из формального математического описания задачи.

 

Факториал
	n! = n * (n-1)!, при n>0 1, n=0	Function Fact(n:byte):longint; begin if n=0 then Fact:=1 else Fact:=n*Fact(n-1) end;
Числа Фибоначчи
	Фn = Фn-1 + Фn-2, при n>1 Ф0 = 1, Ф1 = 1	Function F(n:byte):longint; begin if n <= 1 then F:=1 else F:= F(n-1)+F(n-2) end;

  

Рекурсия и итерация

Рекурсивную программу всегда можно преобразовать в нерекурсивную (итеративную, использующую циклы), которая выполняет те же вычисления. И наоборот, используя рекурсию, любое вычисление, предполагающее использование циклов, можно реализовать, не прибегая к циклам.

К примеру, вычисление факториала и чисел Фибоначчи можно реализовать без рекурсии:

 

Факториал
Function Fact(n:byte):longint; var F, i: byte; begin F:=1; for i:=1 to n do F:=F*i; Fact:=F end;	Function Fact(n:byte):longint; begin if n=0 then Fact:=1 else Fact:=n*Fact(n-1) end;
Числа Фибоначчи
Function F(n:byte):longint; var F0, F1, F2: longint; i: byte; begin F0:=1; F1:=1; for i:=2 to n do begin F2:=F1+F0; F0:=F1; F1:=F2; end; F:=F1 end;	Function F(n:byte):longint; begin if n <= 1 then F:=1 else F:= F(n-1)+F(n-2) end;

При выполнении рекурсивной подпрограммы сначала происходит «рекурсивное погружение», а затем «возврат вычисленных результатов». Например, вычисление 5! при помощи вызова Fact(5) будет происходить следующим образом:

Fact(5)  5 * Fact(4) 5 * 24  120
 ­
4* Fact(3) 4 * 6
 ­
3 * Fact(2) 3 * 2
 ­
2 * Fact(1) 2 * 1
 ­
1  1

Как видно на примере вычисления 5!, при «рекурсивном погружении» функция Fact вызывает точно такой же новый экземпляр самой себя. При этом сама функция как бы еще не завершилась, а новый ее экземпляр уже начинает работать. И только когда новый экземпляр завершит работу («вернет вычисленные результаты»), будет продолжена работа самой функции.

Стек. Информация о таких незавершенных вызовах рекурсивных подпрограмм (а это, в самом простом представлении, значения переменных, необходимых для работы подпрограммы) запоминается в специальной области памяти – стеке. При работе в среде Turbo Pascal содержимое стека и весть процесс появления и завершения рекурсивных вызовов можно просмотреть в окне «Call Stack», которое вызывается нажатием клавиш Ctrl+F3.

Размер стека по умолчанию – 16Кб. Если незавершенных рекурсивных вызов слишком много (хотя вы по ошибке могли написать и программу с бесконечной рекурсией – тогда вам ничто не поможет), то система выдаст сообщение «Stack overflow» («Переполнение стека»). В этом случае есть смысл увеличить размер стека используя меню «Options – Memory Sizes ”.

Также помните, что нажав клавиши Ctrl+O O, вы перед текстом программы получите список значений всех директив компилятора Turbo Pascal, в котором можно изменять признаки их активности и значения, установленные по умолчанию.

{$A+,B-,D+,E-,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 16384,0,655360}

Размер стека определяется первым параметром директивы $M. Второй и третий ее параметры – нижняя и верхняя границы области динамически выделяемой памяти (кучи, heep). Размер стека можно увеличить непосредственно в такой строке, однако эти установки будут действовать только для данной программы.

 

4.3 Сложность рекурсивных вычислений. При относительной простоте написания, у рекурсивных подпрограмм часто встречается существенный недостаток – неэффективность. Так, сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения n. При использовании же рекурсивной функции уже при n=40 заметна задержка при вычислении, а при больших n результат появляется весьма не скоро.

Неэффективность рекурсии проявляется в том, что одни и те же вычисления производятся по многу раз. Так для вычисления 40-го числа Фибоначчи схема рекурсивных вызовов представлена на рисунке ниже.

Оценить сложность рекурсивных вычислений (количество рекурсивных вызовов) можно с помощью рекуррентных соотношений. Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями. Значение любой такой функции можно определить, вычисляя все ее значения начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения.

Рекуррентные выражения используются, в частности, для определения сложности рекурсивных вычислений.

Например, пусть мы пытаемся вычислить числа Фибоначчи по рекурсивной схеме

F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 1; F(1) = 1;

с помощью указанной выше рекурсивной подпрограммы-функции F(n).

Требующееся при вычислении значения F(N) по такой схеме количество рекурсивных вызовов может быть получено из решения рекуррентного выражения

T_N = T_N-1 + T_N-2, при N >= 1; T₀ = 1; T₁ = 1

T_N приблизительно равно Ф^N, где Ф 1.618 - золотая пропорция («золотое сечение»), т.е. приведенная выше программа потребует экспоненциальных временных затрат на вычисления.