Основы алгоритмизации в информационных системах. Белов М.П. - 9 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

тата после конечного числа шагов.
Массовость – означает, что алгоритм решения задачи разрабатывается в
общем виде, т.е. он должен быть применим для некоторого класса задач, разли-
чающихся лишь исходными данными. При этом исходные данные могут выби-
раться из некоторой области, которая называется областью применимости
алгоритма.
1.3. Основные характеристики алгоритмов
Для решения одной и той же задачи как правило можно использовать
различные алгоритмы. В связи с этим, возникает необходимость сравнивать
их между собой, и для этого нужны определенные критерии качества алго-
ритмов.
Временные характеристики алгоритма определяют длительность ре-
шения или временную сложность [4].
Длительность решения часто выражается в единицах времени, но удоб-
нее ее выражать через количество операций, так как количество операций не
зависит от быстродействия конкретной машины.
Временной сложностью алгоритма называется зависимость времени
счета, затрачиваемого на получение результатов от объема исходных данных.
Временная сложность позволяет определить наибольший размер задачи,
которую можно решить с помощью данного алгоритма на ПК. Каждый алго-
ритм можно характеризовать функцией f(n), выражающей скорость роста объ-
ема вычислений при увеличении размерности задачи – n. Если эта зависимость
имеет линейный или полиномиальный характер, то алгоритм считается
″хорошим″, если экспоненциальный – ″плохим″.
Для сложных задач эта характеристика имеет большое значение, т.к. ее
изменение значительно сильнее влияет на время решения, чем изменение бы-
стродействия ПК. Например, при зависимости f(n) = 2
n
увеличение произво-
дительности в 10 раз увеличивает размерность задачи, решаемой за то же вре-
мя, всего на 15% [4].
Объемные характеристики алгоритма определяют его информационную
сложность. Информационная сложность связана со сложностью описания, нако-
пления и хранения исходных, промежуточных и результирующих данных при
решении определенной задачи.
Объем текста алгоритма (программы) определяется количеством операто-
9

Страницы