Метрическая А. т.
А. т. можно разделить на дескриптивную (качественную) и метрическую
(количественную). Первая исследует алгоритмы с точки зрения устанавливаемого
ими соответствия между исходными данными и результатами, к ней относятся,
в частности, те алгоритмические проблемы, о к-рых говорилось в предыдущем
разделе. Вторая исследует алгоритмы с точки зрения сложности как самих
алгоритмов, так и задаваемых ими "вычислений", т. е. процессов последовательного
преобразования конструктивных объектов. Важно подчеркнуть, что сложность
алгоритмов и вычислений может определяться различными способами, причём
может оказаться, что при одном способе А будет сложнее В, а при другом
способе - наоборот. Чтобы говорить о сложности алгоритмов, надо сперва
описать к.-л. точный язык для записи алгоритмов и затем под сложностью
алгоритма понимать сложность его записи; сложность же записи можно определять
различными способами (напр., как число символов данного типа, участвующих
в записи, или как набор таких чисел, вычисленных для разных типов символов).
Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление
представляется в виде цепочки сменяющих друг друга конструктивных объектов
и что считается сложностью такой цепочки (только ли число членов в ней
<-
"число шагов" вычисления или ещё учитывается "размер" этих членов и
т. п.); в любом случае сложность вычисления зависит от исходного данного,
с к-рого начинается вычисление, поэтому сложность вычисления есть функция,
сопоставляющая с каждым объектом из области применимости алгоритма сложность
соответствующей цепочки. Разработка методов оценки сложности алгоритмов
и вычислений имеет важное теоретич. и практич. значение, однако в отличие
от дескриптивной А. т., оформившейся в целостную матем. дисциплину, мет-рич.
А. т. делает лишь первые шаги.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я