Сложность рекурсивных алгоритмов.

Сложность рекурсивных алгоритмов оценить непросто в силу вложенности алгоритмических структур

f(n)  f(n* f(n-1))

Например, для рекурсивного вычисления алгоритма n! Сложность будет зависеть от сложности каждого из алгоритмов, входящих в рекурсию.

В общем случае T(n) ~ O(N).

Другие рекурсивные алгоритмы в общем случае имеют временную сложность T(n) ~ O(aⁿ), где a=const, что в результате дает суммарную сложность, большую, чем сложность не рекурсивного алгоритма решения этой же задачи.

Тема 2. Традиционные подходы в теории алгоритмов.

2.1 Рекурсивные функции.

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

Пусть задана некоторая функция  = f(x₁, x₂, …, x _n).

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

Тогда рекурсивными функциями называют частный случай вычислимых функций. Алгоритмы, являющиеся правилами задания функций, называют алгоритмами, сопутствующими рекурсивным функциям (АСФ).

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

Базовые рекурсивные функции могут быть трех типов:

1) Функции любого числа независимых переменных, тождественно равные нулю _n()=0,где n – число аргументов функции (n может быть равным нулю).

Например:

АСФ в данном случае гласит: если задана функция _n ,то для любой совокупности значений аргументов значение функции равно нулю.

2) Тождественные функции любого числа независимых переменных _n,i, где n – число аргументов функции, i – номер одного из аргументов.

АСФ гласит: если задана функция _n,i, то значение функции равно значению i-го аргумента (слева направо).

Например:

_3,2(5, 8, 0)=8

_1,1(6)=6

Для тождественных функций:

3) Функции следования одного независимого переменного (х).

АСФ гласит: если задана функция (х), то значением функции нужно считать число, непосредственно следующее за числом, являющимся значением аргумента.

При этом (х)=х’ – последователь аргумента.

Например: (5)=5’=6

Операторы рекурсии.

1. Оператор суперпозиции (подстановки) S. Этот оператор по заданной функции F(f₁,f₂,…,f_n) строит новую функцию Ф, такую, что для нее справедливо тождество:

Ф= F(f₁,f₂,…,f_n), где f_i – значение некоторых функций.

Формальная запись оператора суперпозиции выглядит следующим образом:

Ф::=S[ F, f₁, f₂,, …, f_n],

где знак ::= обозначает «равно по определению».

Например, если функция F=(f₁) задана как функция следования, а функция (y)=f₁, то, согласно оператору суперпозиции, получаем некоторую функцию

(y)::=S[(f₁); (y)]

Ее числовое значение определяется:

(y)= ((y))= (y’)=y’’

(5)=7

2. Оператор рекурсии R. Этот оператор строит по двум функциям f1_n-1 и f2_n+1 новую функцию f_n.

Формальная запись:

f::=R[f1, f2, x, (y)],

где переменная х – главный дополнительный аргумент;

у – вспомогательный аргумент.

При описании сущности оператора рекурсии принято не указывать аргументы первой из заданных функций ни при ее записи, ни в записях других функций, подразумевая эти аргументы. В этом случае говорят, что оператор рекурсии задает новую функцию с помощью двух условий:

Здесь f1  f1(x₁, x₂,…, x_n-1, 0 ), x=0

i’ – последователь текущего аргумента.

АСФ в данном случае гласит: значением получаемой функции для х=0 (главный дополнительный элемент) считать значение исходной функции f1(x₁, x₂,…, x_n ).

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

Например, пусть f1=₀=0 (n=0), f2=_2,1(x, y)=X (n=2), тогда некоторая новая функция Z(x)::=R[₀,, _2,1(x, y); X, (y)] удовлетворяет следующим условиям:

Т. о. Z(1)=0, Z(2)=1, Z(3)=2 и т. д.

3. Оператор минимизации  (оператор построения по первому нулю). Этот оператор по заданной функции, зависящей от n+1 аргументов, строит новую функцию, зависящую от n аргументов. При этом исключаемый аргумент является вспомогательным.

Формальная запись:

f ::= [f1; (x)]

АСФ гласит: придавать вспомогательному аргументу (х) последовательные значения, начиная с 0 до тех пор, пока не окажется, что функция f₁ становится равной нулю в первый раз, полученное значение вспомогательного аргумента х^* считать значением искомой функции f.

Замечание: Базовые функции и функции, получаемые при помощи операторов S и R определены для любых значений аргументов, чего не следует для функций, полученных через оператор , поскольку для многих комбинаций аргументов функции f₁ они могут быть не определены, т.к. исходная функция не обращается в ноль.

Например:

f₁=_2,1(x, y)

(x)::= [_2,1(x, y); (y)]

(0)=0, (i) не существует при i  0

Пусть i=2.

_2,1(2, 0)=2

_2,1(2, 1)=2

Т. о. при любых значениях у эта функция возвращает один и тот же результат.

Вывод: Рекурсивными называются базовые функции и любые функции, полученные из них с помощью конечного числа операторов S, R, .

Примеры рекурсивных функций:

1) y = x+1 = (x) = x’.

2) _3,3(x, y, z)=z

Если z^*:z(z+1), то f^*(x, y, z^*)::=S[_3,3; z+1]=z+1

С помощью введенной функции f^* и базовой функции _1,1(x)=x можно определить новую функцию F(x, y) как рекурсивную функцию

F(x, y)::=R[_1,1(x), f^*(x, y, z^*), y, (z)], удовлетворяющую следующим условиям:

3) Можно показать, что функция =x*y является рекурсивной. Это же справедливо и для других арифметических операций. Т. о. можно сделать вывод, что алгоритмы являются рекурсиями.

Гипотеза Черча: понятием рекурсивной функции исчерпывается полностью понятие вычислимой функции.

На основе этой гипотезы российские ученые Колмогоров и Успенский сделали обобщение: если существует некоторая рекурсивная функция, то для нее всегда можно построить алгоритм. И наоборот, любой существующий алгоритм может быть выражен в понятиях рекурсивной функции.

Невозможность создания рекурсивной функции для решаемой задачи означает невозможность реализации алгоритма ее решения.

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