64. Оценка сложности рекурсивных алгоритмов
Рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
unsigned int factorial(unsigned int n) { if(n > 1) return n*factorial(n-1); else return 1; end; Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N). Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее. Рассмотрим такую процедуру: int doubleRecursive(int n) { doSomething(); if(n > 0) { doubleRecursive(N-1); doubleRecursive(N-1); } } Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1) = O(2^N). Замечательный рисунок моего авторства:
Вот и всё. Удачного экзамена!