Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

СЛОЖНОСТЬ АЛГОРИТМОВ

ПОНЯТИЕ ТРУДОЕМКОСТИ АЛГОРИТМА

Трудоемкость алгоритма — это количество операций, которые необходимо выполнить в процессе решения поставленной задачи с помощью этого алгоритма. Практические оценки трудоемкости вычислительных алгоритмов, как правило, осуществляются раздельно для разных операций с группированием только однородных действий, таких как сложение и вычитание. Операции умножения и деления существенно различаются по длительности, поэтому оцениваются раздельно. В алгоритмах сортировки следует раздельно учитывать количества операций сравнения и перестановок. В алгоритмах поиска достаточно оценить только количество операций сравнения.

Трудоемкость алгоритма может зависеть от следующих свойств исходных данных:

  • 1) объем данных (длина входа);
  • 2) конкретика значений данных;
  • 3) порядок поступления данных с конкретными значениями.

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

Например, количество операций при вычислении значения полинома существенно зависит от количества нулевых коэффициентов, а при сортировке массива — от исходного порядка следования элементов (при благоприятном раскладе — перестановки данных могут не потребоваться вовсе).

Зависимость количества выполняемых операций от длины входа л называется функцией трудоемкости /(л). Зависимость трудоемкости от конкретики значений и порядка поступления данных обусловливает изменчивость количества выполняемых операций при фиксированном л, и функция трудоемкости /(л) становится случайной функцией. Поэтому можно вести речь о минимальном /mjn (л), максимальном /тах (л) и среднем количестве /(л) операций, выполняемых исполнителем алгоритма при конкретной длине входа.

Часто анализ алгоритмов осуществляется упрощенно — их трудоемкость оценивается при больших объемах входных данных, т.е. при л —> Такой анализ называется асимптотическим.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы