Сложность алгоритмов. Классы сложности Р и ЕХР.

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

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

Практически важный аспект анализа сложности связан с классификацией алгоритмов по типу зависимости T(V) по скорости ее роста. Существуют алгоритмы, в которых T(V) растет линейно, квадратично, имеет кубическую зависимость и т.д. Такие алгоритмы принято называть полиномиальными или алгоритмами с полиномиальной сложность и говорить, что алгоритм относится к классу сложности P. Существую алгоритмы, временная сложность которых растет быстрее полинома любой степени, как  c некоторым основанием a. Такие алгоритмы принято называть алгоритмами с экспоненциальной сложностью и говорить, что алгоритм относится к классу сложности EXP.

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

 

*70. Примеры оценки сложности алгоритмов.

 

Понятие подпрограммы.

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

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

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

 

Итерация и рекурсия.

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

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

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

 

⇐ Предыдущая234567891011

Поделиться: