Понятие сложности алгоритма

Проблема эквивалентности

Проблема эквивалентности сформулирована следующим образом не существует общего метода определения эквивалентности алгоритмов.

Следовательно, программист должен доказать, что его программа:

1. действительно решает ту задачу, для которой она разработана,

2. будет надежно функционировать в другой среде.

Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.

Виды сложности:

вычислительная (временная);

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

сложность текста алгоритма характеризует исполнителя (например, ЭВМ), его язык, а не метод решения задач;

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

Сложность алгоритма выражают в виде функции от объема входных данных.

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

Обозначим:

Т(п) – время выполнения алгоритма,

F – некая функция от п.

Будем говорить, что Т(п) – время выполнения алгоритма А – имеет порядок роста f(п) при , или по-другому, алгоритм имеет теоретическую сложность О(f(п)), если найдется такая постоянная С>0 и число п₀, что Т(п) С* f(п) при всех п>=п₀.

Здесь предполагается, что f(п) неотрицательно, по крайней мере при п>=п₀.

2 декабря

СРС: Составить дерево к структурам данных.