23.Мера сложности

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

Под пространственной эффективностью понимают объём памяти, требуемой для выполнения программы.

Временная эффективность программы определяется временем, необходимым для ее выполнения.

Самым простым способом оценить алгоритм - сопоставить ему число элементарных операций в описании. При реализации это может быть число команд в программе или объём памяти, которую занимает программа. В этом случае оценка алгоритма A есть некоторое число k: (A) = k.

Более интересной может быть оценка пары: алгоритма A и конкретной задачи , которая им решается. Например, оценкой может быть объем памяти под программу, исходные и промежуточные данные, необходимые для решения данной задачи, или время для решения данной задачи с помощью алгоритма A. В любом случае это будет число (A()) = k().

Свойство массовости алгоритма предполагает, что алгоритм будет использоваться для решения класса A подобных задач, с разными исходными данными. Поэтому более сложной оценкой будет оценка как функция свойства задачи. Cопоставим каждой задаче из класса задач, решаемым алгоритмом, некоторый вектор числовых параметров задачи N = (n1, n2, …, nt). В этом случае оценка (A(A)) = k(N), и это уже будет функция от параметров задачи.