Анализ функции сложности по программе

Программист должен уметь проводить анализ алгоритмов и определять их сложность. Временная сложность алгоритма может быть подсчитана исходя из анализа его управляющих структур. Алгоритмы без циклов и рекурсивных вызовов имеют кон­стантную сложность. Если нет рекурсии и циклов, все управляющие структуры могут быть сведены к структурам констант­ной сложности. Следовательно, и весь алгоритм также характе­ризуется константной сложностью. Определение сложности алгоритма в основном сводится к анализу циклов и рекурсивных вызовов. Например, рассмотрим алгоритм обработки элементов массива (рис.11.1а).

Сложность этого алгоритма O(N), так как тело цикла выпол­няется N раз, и сложность тела цикла равна O(1). Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной (рис.11.1б), то вся конструкция характеризуется квадратичной сложностью. Сложность такой программы — O(N²).

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

а) б)

Рисунок 11.1 – Блок-схема алгоритма подпрограммы обработки одномерного (а) и двумерного массива (б)

В качестве примера возьмем программу, содержащую медленную процедуру Slow со сложностью порядка O(N²) и быструю процедуру Fast со сложностью порядка O(N) – рис.11.1. Сложность всей программы зависит от соотношения между этими двумя процедурами.

Если при выполнении циклов процедуры Fast всякий раз вызывается проце­дура Slow, то сложности процедур перемножаются. Общая сложность равна про­изведению обеих сложностей. В данном случае сложность алгоритма составляет O(N) * O(N²)или О(N * N²) = O(N³).

С другой стороны, если основная программа вызывает процедуры отдельно, их вычислительная сложность складывается. В этом случае итоговая сложность по порядку величины равна O(N) + O(N²) = O(N²).

Рассмотрим алгоритм рис.11.2, который для матрицы A[NxN] находит максимальный элемент в каждой строке.

Рисунок 11.2 – Фрагмент алгоритма поиска максимального элемента в каждой строке массива

В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N²).

O(f)=O(N)*(O(1)+(O(N)*(O(1)+O(1)))+O(1))=O(N)*O(N)=O(N²)

Как правило, около 90% времени работы программы требу­ет выполнение повторений и только 10% составляют непосредственно вычисления. Анализ сложности программ показывает, на какие фрагменты выпадают эти 90% — это циклы наиболь­шей глубины вложенности. Повторения могут быть организова­ны в виде вложенных циклов или вложенной рекурсии.

Эта ин­формация может использоваться программистом для построе­ния более эффективной программы следующим образом. Прежде всего можно попытаться сократить глубину вложенности повторений. Затем следует рассмотреть возможность сокра­щения количества операторов в циклах с наибольшей глубиной вложенности. Если 90% времени выполнения составляет вы­полнение внутренних циклов, то 30%‑ное сокращение этих не­больших секций приводит к 27%‑ному снижению времени вы­полнения всей программы.

Порядок выполнения лабораторной работы

Определить величину сложности алгоритма задачи лабораторной работы №9. В отчете необходимо также привести все сопутствующие расчеты сложности алгоритма.

Контрольные вопросы

1) Что определяет функция сложности алгоритма?

2) Укажите виды функции сложности алгоритмов.

3) Каким образом определяется временная функция сложности алгоритма?

4) Укажите способы анализа функции сложности по алгоритму.

5) Укажите уравнение, по которому определяется функция сложности.

ЛАБОРАТОРНАЯ РАБОТА № 12

Тема: «Исследование рекурсивных и итерационных алгоритмов»

Цель работы – изучить принцип построения рекурсивных и итерационных алгоритмов.

Теоретические сведения

Рекурсия

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

Классическим примером рекурсивной функции является функция вычисления факториала. Для того чтобы получить значение факториала числа n, требуется умножить на n факториал числа (n – 1).

На рис.12.1 показана блок схема алгоритма подпрограммы, которая производит рекурсивное зацикливание: будет выводиться значение «1», после чего подпрограмма снова будет вызывать себя и т.д. до бесконечности. Поскольку при каждом вызове подпрограммы в программный стек помещается ее запись активации, то, в конце концов, программный стек переполнится, и программа завершится с ошибкой. Таким образом, чтобы рекурсия завершалась, необходимо, чтобы рекурсивный вызов происходил не всегда, а лишь при выполнении некоторого условия.

Рисунок 12.1 – Пример подпрограммы с рекурсивным зацикливанием

Рассмотрим рекурсивные подпрограммы рис.12.2.

а) б)

Рисунок 12.2 – Примеры подпрограмм с применением рекурсии

При вызове процедуры p(5) рис.12.2а выводится значение «5», вызывается процедура p(4); затем выводится «4» и вызовется p(3) и т.д. до вызова p(0), когда выводится «0» и, поскольку условие n>0 станет ложным, рекурсия завершится. Итак, в результате вызова p(5) на экран будет выведено «5 4 3 2 1 0».

При вызове подпрограммы p(5) рис.12.2б вначале проверится условие n>0 и, поскольку оно истинно, вызовется p(4), затем p(3) и т.д. до p(0). Так как при вызове p(0) условие n>0 уже не выполняется, то осуществится вывод 0 и произойдет выход из вызова p(0) в вызов p(1) сразу после условного оператора. Далее осуществится вывод «1» и выход из вызова p(1). В результате на экран будет выведено «0 1 2 3 4 5». Процесс возврата из уже сделанных рекурсивных вызовов продолжится, пока не будет осуществлен выход из вызова p(5).

Схема рекурсивных вызовов подпрограмм на рис.12.2 изображена на рис.12.3:

Рисунок 12.3 – Схема рекурсивных вызовов спуска и возврата

Процесс рекурсивных вызовов называется рекурсивным спуском, а процесс возврата из них – рекурсивным возвратом. Глубиной рекурсии называется максимальное число вложенных рекурсивных вызовов (в нашем примере глубина рекурсии равна 5). Число вложенных рекурсивных вызовов в данный момент выполнения программы называется текущим уровнем рекурсии.

Несколько замечаний, относительно целесообразности применения рекурсивных подпрограмм:

а) Рекурсивные алгоритмы являются эффективным средством программирования для некоторого класса задач: сложные задачи численного анализа, комбинаторики, алгоритмов трансляции, операций над списковыми структурами и т. д. Программы в этом случае имеют небольшие объемы по сравне­нию с итерацией и требуют меньше времени на отладку.

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

в) Накладные расходы на рекурсивные вызовы достаточно велики, поэтому если есть явное нерекурсивное решение, то следует предпочесть его.

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

Итерационные циклы

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

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

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

Пример 12.1. Вычислить значение функции Sin(Х) по приближенной формуле F=sin(X) = X - X³/3! + X⁵/5! - … с погрешностью Е = 10^-5.

Функция F представляет собой сумму членов степенного ряда: F = U1 + U2 +... + Un. Условие окончания вычисления функции F: |Un – Un+1 | ≤ E, где Un – общий член ряда; Un+1 – следующее слагаемое. Un+1 через Un можно определить как:

Схема алгоритма задачи приведена на рис.12.4.

Рисунок 12.4 – Алгоритм решение задачи итерационных циклов

Индивидуальные задания

Написать алгоритм решения задачи, используя рекурсию.

1) Описать рекурсивный алгоритм для вычисления n!.

2) Описать рекурсивный алгоритм для вычисления xⁿ.

3) Описать рекурсивный алгоритм pow(x,n) от вещественного x (x≠0) и целого n, которая вычисляет величину xⁿ согласно формуле

4) Рекурсивно найдите максимальный элемент в одномерном массиве.

5) Используя рекурсивный алгоритм, найти n-ый член последовательности

6) Используя рекурсивный алгоритм, найти сумму первых n членов последовательности из предыдущего примера.

7) Используя рекурсию, найти максимальный элемент из n членов последовательности, вводимых с клавиатуры.

8) Используя рекурсию, найти максимальный элемент из первых n членов последовательности

9) Используя рекурсию, вывести первые n членов последовательности , которые больше m.

10) Используя рекурсию, распечатать номера первых n членов последовательности x_n=2*x_n-3+3*x_n-1-4, x₀=2, x₁=0, x₂=1,, которые больше m.

11) Составьте алгоритм вычисления суммы .

12) Определите n–й член последовательности, в которой каждый следующий член равен сумме всех предыдущих.

Контрольные вопросы

1) На чем основан рекурсивный метод программирования?

2) В чем разница между «циклическим» и «рекурсивным» способами определения? Какой элемент является обязательным в рекурсивном определении?

4) К чему приводит «рекурсивное зацикливание»?

5) Какое условие должно обязательно присутствовать в любой рекурсивной процедуре?

6) Что такое явная и косвенная рекурсии?

ЛАБОРАТОРНАЯ РАБОТА № 13

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: