СЛОЖНОСТЬ АЛГОРИТМОВ
ПОНЯТИЕ ТРУДОЕМКОСТИ АЛГОРИТМА
Трудоемкость алгоритма — это количество операций, которые необходимо выполнить в процессе решения поставленной задачи с помощью этого алгоритма. Практические оценки трудоемкости вычислительных алгоритмов, как правило, осуществляются раздельно для разных операций с группированием только однородных действий, таких как сложение и вычитание. Операции умножения и деления существенно различаются по длительности, поэтому оцениваются раздельно. В алгоритмах сортировки следует раздельно учитывать количества операций сравнения и перестановок. В алгоритмах поиска достаточно оценить только количество операций сравнения.
Трудоемкость алгоритма может зависеть от следующих свойств исходных данных:
- 1) объем данных (длина входа);
- 2) конкретика значений данных;
- 3) порядок поступления данных с конкретными значениями.
Объем исходных данных решающим образом влияет на трудоемкость практически всех алгоритмов, но и конкретика данных весьма существенна.
Например, количество операций при вычислении значения полинома существенно зависит от количества нулевых коэффициентов, а при сортировке массива — от исходного порядка следования элементов (при благоприятном раскладе — перестановки данных могут не потребоваться вовсе).
Зависимость количества выполняемых операций от длины входа л называется функцией трудоемкости /(л). Зависимость трудоемкости от конкретики значений и порядка поступления данных обусловливает изменчивость количества выполняемых операций при фиксированном л, и функция трудоемкости /(л) становится случайной функцией. Поэтому можно вести речь о минимальном /mjn (л), максимальном /тах (л) и среднем количестве /(л) операций, выполняемых исполнителем алгоритма при конкретной длине входа.
Часто анализ алгоритмов осуществляется упрощенно — их трудоемкость оценивается при больших объемах входных данных, т.е. при л —> Такой анализ называется асимптотическим.
