Анализ алгоритма точного решения задачи о сумме
Рассмотрим лучший и худший случай для данного алгоритма:
a. В лучшем случае, когда последний элемент массива совпадает со значением V: V=S[N],необходимо выполнить только одно суммирование, что приводит к оценке: 
(N)=Q(N);
b. В худшем случае, если решения вообще нет, то придется проверить все варианты, и 
(N) = Q (N* 
).
Получим детальную оценку для худшего случая, используя принятую методику подсчета элементарных операций:
(N) = 2+N*(3+2)+2+( -1)*{2+N*(3+5)+1+1+ 
+2+2} (7.2)
Для получения значения - количества операций, необходимых для увеличения счетчика на «1» рассмотрим по шагам проходы цикла While, в котором выполняется эта операция:
| CNT | Количество проходов в While | Операций |
| 001 | 1 | 6+2 |
| 010 | 0 | 2 |
| 011 | 2 | 2*6+2 |
| 100 | 0 | 2 |
| 101 | 1 | 6+2 |
| 110 | 0 | 2 |
| 111 | 3 | 3*6+2 |
РЕКУРСИВНЫЕ ФУНКЦИИ И АЛГОРИТМЫ
Рекурсивные функции
а) Терминологическое введение
По сути один и тот же метод, применительно к различным областям носит различные названия – это индукция, рекурсия и рекуррентные соотношения – различия касаются особенностей использования.
Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.
Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.
|
|
|
Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:
б) Примеры рекурсивного задания функций
| 1. | 
| f(0)=0 f(n)= f(n-1)+1 |
| 2. |
| f(0)=1 f(n)= n*f(n-1) |
Последовательная подстановка дает – f(n)=1*2*3*…*n = n!
Для полноты сведений приведем формулу Стирлинга для приближенного вычисления факториала для больших n: 
| 3. |
| f(0)=1 f(1)=1 f(n)= f(n-1)+ f(n-2), n>=2 |
Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически 
| 4. |
| f(0)=1 f(n)= f(n-1)+ f(n-2)+…+1 =  f(i)+1
|
Для получения функции в явном виде рассмотрим ее последовательные значения: f(0)=1, f(1)=2, f(2)=4, f(3)=8, что позволяет предположить, что f(n)= 
, точное доказательство выполняется по индукции.
| 5. |
| f(0)=1 f(n)= 2*f(n-1) |
Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения – f(n)= , как и в примере 4, что проверяется элементарной подстановкой.
|
|
|
| 6. |
| f(0)=1 f(1)=2 f(n)= f(n-1)*f(n-2) |
В этом случае мы можем получить решение в замкнутой форме, сопоставив значениям функции соответствующие степени двойки:
Обозначив через Fn - n-ое число Фибоначчи, имеем: f(n)= 
.
Дата добавления: 2018-02-28; просмотров: 452; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!