3.1 Расчет трудоемкости алгоритма
При расчете трудоемкости алгоритма используются универсальный (машинный) и сетевой методы. Исходной информацией при расчете является граф алгоритма, приведенный на рис.3.1.
Рисунок 3.1 — Граф алгоритма
Вероятности перехода для графа:
Среднее число ni обращений к операторам алгоритма определяется корнями системы линейных алгебраических уравнений:
Гдеnj — вершина, которая рассматривается по отношению к i-вершине;
ij — символ Кронекера;
Pji — вероятность перехода;
Значение ni определяется решением системы линейных алгебраических уравнений:
На основе заданного графа строим систему из 10 уравнений:
Произведем расчет корней системы уравнений с помощью программы tminmax.exe. Результат машинного расчета приведен в ПРИЛОЖЕНИИ А.
Рассчитаем среднюю, минимальную и максимальную трудоемкости заданного алгоритма сетевым методом.
Сначала рассчитываем среднюю трудоемкость алгоритма.
Прежде всего необходимо устранить ВСЕ циклы, начиная со внутренних (с меньшим рангом). Для этого отдельно вырисовываем цикл с наименьшим рангом:
Рисунок 3.2 — Наименьший цикл графа
Определим для него среднее число обращений к каждой из операторных вершин при одном прогоне алгоритма:
Следовательно, можно заменить цикл С1 одной вершиной со средней трудоемкостью Kc1.
Далее, устраняем следующий цикл, С2:
Рисунок 3.3 — Цикл графа С2
Рисунок 3.4 — Конечный графа
Теперь можно посчитать среднюю трудоемкость всего алгоритма:
Далее рассчитываем минимальную и максимальную трудоемкости алгоритма.
Устраняем все циклы, начиная со внутренних (рис. 3.2):
Таким образом, вычислены минимально и максимально возможные значения трудоемкости для цикла С1.
Аналогично, для цикла С2 (рис. 3.3):
Для конечного графа (рис. 3.4):
Таким образом, минимальная и максимальная трудоемкости всего алгоритма равны соответственно:
Анализ трудоёмкости алгоритмов
Целью анализа трудоёмкости алгоритмов является нахождение оптимального алгоритма для решения задачи.
В качестве критерия оптимальности алгоритма выбирается трудоемкость алгоритма, понимаемая как количество элементарных операций, которые надо выполнить для решения задачи с помощью данного алгоритма.
Функцией трудоемкости называется отношение, связывающие входные данные алгоритма с количеством элементарных операций.
Одним из упрощенных видов анализа, является асимптотический анализ алгоритмов.
Целью асимптотического анализа является сравнение затрат времени и других ресурсов при использовании различных алгоритмов, предназначенных для решения одной и той же задачи, при больших объемах входных данных.
Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных.
Для описания скорости роста функций используется асимптотическая оценка O.
Она представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма и позволяет определить, как быстро растет трудоемкость алгоритма с увеличением объема данных.
Определение. T(n) = O(f(n)), если существуют константы c > 0, n0 > 0 такие, что выполняется неравенство: 0 T(n) cf(n) для любого n >= n0
Здесь n — величина объёма данных.
Иначе говоря, запись T(n) = O(f(n)) означает, что T(n) принадлежит классу функций, которые растут не быстрее, чем функция f(n) с точностью до постоянного множителя.
Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя.
Напр., если говорят, что алгоритму требуется время порядка O(n 2 ), то имеют в виду, что время выполнения задачи растет не быстрее, чем квадрат количества элементов.
Пример. Функция T(n) = 3n 3 +2n 2 имеет степень роста O(n 3 ), т.е. время выполнения задачи растет не быстрее, чем куб количества исходных данных. Если c = 5, n0 = 0, то 3n 3 +2n 2 n 3
При оценке трудоемкости используют правило сумм: в общем случае трудоемкость выполнения программных фрагментов имеет порядок фрагмента с наибольшим временем выполнения.
Пример. Пусть есть три фрагмента с временами выполнения O(n 3 ), O(n 2 ), O(nlogn). Тогда время выполнения первых двух фрагментов – это максимум из первых двух оценок — O(n 3 ). Затем сравнивается результат и третья оценка.
Для всех трех — O(n 3 ).
При оценке трудоемкости используется также правило произведений: если T1(n) и T2(n) имеют степени роста O(f(n)) и O(g(n)) соответственно, то произведение T1(n)T2(n) имеет степень роста O(f(n))O(g(n)).
Например, O(n 2 / 2) эквивалентно O(n 2 ).
Скорость роста некоторых функций:
n log n n*log n n 2
256 8 2048 65536
4096 12 49152 16777216
65536 16 1048565 4294967296
1048476 20 20969520 1099301922576
16775616 24 402614784 281421292179456
Из таблицы видно, что для задач с небольшим значением n метод решения задачи не влияет на скорость, но по мере роста n время, нужное для получения решения, становится большим (10 7 секунд равно 3,8 месяца, 10 8 секунд – 3,1 года).
Оценка Ώ задает нижнюю асимптотическую оценку роста функции T(n) и определяет класс функций, которые растут не медленнее, чем f(n) с точностью до постоянного множителя.
Определение. T(n) = Ώ(f(n)), если существуют константы c > 0, n0 > 0 такие, что выполняется неравенство: T(n) >= cf(n) >= 0 для любого n >= n0.
Например, запись T(n) = Ώ(nlog(n)) обозначает класс функций, которые растут не медленнее, чем f(n) = nlog(n).
(В этот класс попадают все полиномы со степенью, большей единицы, равно как и все степенные функции с основанием большим единицы).
Для задания одновременно верхней и нижней оценки роста функции T(n) используется оценка Ө (“тэта большое”).
Определение. T(n) = Ө(f(n)), если при f > 0 и n > 0 существуют константы c1, c2, n0 такие, что выполняется неравенство: c1f(n) T(n) c2f(n) для любого n >= n0.
Функция f(n) является асимптотически точной оценкой функции T(n), т.к. по определению функция T(n) не отличается от функции f(n) с точностью до постоянного множителя.
Например, для метода пирамидальной сортировки оценка трудоёмкости составляет T(n) = Ө(nlog(n)), то есть f(n) = nlogn.
Равенство T(n) = Ө(f(n)) выполняется тогда и только тогда, когда T(n) = O(f(n)) и T(n) = Ώ (f(n)).
Важно понимать, что Ө(f(n)) представляет собой не функцию, а множество функций, описывающих рост T(n) с точностью до постоянного множителя.
Асимптотические оценки можно представить в порядке увеличения скорости их роста:
Теория алгоритмов
При использовании алгоритмов для решения практических задач мы сталкиваемся с проблемой рационального выбора алгоритма решения задачи. Решение проблемы выбора связано с построением системы сравнительных оценок, которая в свою очередь существенно опирается на формальную модель алгоритма.
Будем рассматривать в дальнейшем, придерживаясь определений Поста, применимые к общей проблеме, правильные и финитные алгоритмы, т.е. алго-ритмы, дающие 1-решение общей проблемы. В качестве формальной системы будем рассматривать абстрактную машину, включающую процессор с фонНеймановской архитектурой, поддерживающий адресную память и набор «элементарных» операций соотнесенных с языком высокого уровня.
-
В целях дальнейшего анализа примем следующие допущения:
каждая команда выполняется не более чем за фиксированное время;
исходные данные алгоритма представляются машинными словами по битов каждое.
Конкретная проблема задается N словами памяти, таким образом, на входе алгоритма – = N* бит информации. Отметим, что в ряде случаев, особенно при рассмотрении матричных задач N является мерой длины входа алгоритма, отражающей линейную размерность.
Программа, реализующая алгоритм для решения общей проблемы состоит из М машинных инструкций по битов – = М* бит информации.
-
Кроме того, алгоритм может требовать следующих дополнительных ресурсов абстрактной машины:
– память для хранения промежуточных результатов;
– память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов).
При решении конкретной проблемы, заданной N словами памяти алгоритм выполняет не более, чем конечное количество «элементарных» операций абстрактной машины в силу условия рассмотрения только финитных алгоритмов. В связи с этим введем следующее определение:
Определение 4.1. Трудоёмкость алгоритма.
Под трудоёмкостью алгоритма для данного конкретного входа – (N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.
Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной системы, требуемых алгоритмом для решения конкретных проблем. Очевидно, что для различных областей применения веса ресурсов будут различны, что приводит к следующей комплексной оценке алгоритма:
, где – веса ресурсов.
Система обозначений в анализе алгоритмов
При более детальном анализе трудоемкости алгоритма оказывается, что не всегда количество элементарных операций, выполняемых алгоритмом на одном входе длины N, совпадает с количеством операций на другом входе такой же длины. Это приводит к необходимости введения специальных обозначений, отражающих поведение функции трудоемкости данного алгоритма на входных данных фиксированной длины.
Пусть – множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D є – задание конкретной проблемы и |D| = N.
В общем случае существует собственное подмножество множества , включающее все конкретные проблемы, имеющие мощность N:
обозначим это подмножество через : = ;
обозначим мощность множества через —> = | |.
-
Тогда содержательно данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Ведем следующие обозначения:
(N) – худший случай – наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:
— худший случай на
(N) – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:
– лучший случай на
(N) – средний случай – среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:
– средний случай на
Классификация алгоритмов по виду функции трудоёмкости
В зависимости от влияния исходных данных на функцию трудоемкости алгоритма может быть предложена следующая классификация, имеющая практическое значение для анализа алгоритмов:
1.Количественно-зависимые по трудоемкости алгоритмы
Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:
Примерами алгоритмов с количественно-зависимой функцией трудоемкости могут служить алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д.
2.Параметрически-зависимые по трудоемкости алгоритмы
Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:
(D) = (,…,) = (,…,), m = = 1 (количество объектов на входе и количество операций – положительные числа), тогда:
f(n) = (g(n)), если существуют положительные с1, с2, n0, такие, что:
с1 * g(n) = n0
Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя.
Отметим, что из f(n) = (g(n)) следует, что g(n) = (f(n)).
2) f(n)=(1) – запись означает, что f(n) или равна константе, не равной нулю, или f(n) ограничена константой на : f(n) = 7+1/n = (1).
2. Оценка О (О большое)
В отличие от оценки , оценка О требует только, что бы функция f(n) не превышала g(n) начиная с n > n0, с точностью до постоянного множителя:
c > 0, n0 > 0 : 0 = n0
Вообще, запись O(g(n)) обозначает класс функций, таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя, поэтому иногда говорят, что g(n) мажорирует функцию f(n).
Например, для всех функций:
f(n)=1/n, f(n)= 12, f(n)=3*n+17, f(n)=n*Ln(n), f(n)=6* +24*n+77 будет справедлива оценка О()
Указывая оценку О есть смысл указывать наиболее «близкую» мажорирующую функцию, поскольку например для f(n)= справедлива оценка О(), однако она не имеет практического смысла.
3. Оценка (Омега)
В отличие от оценки О, оценка является оценкой снизу – т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:
- Введение в теорию алгоритмов
- Машина Поста
- Машина Тьюринга и алгоритмически неразрешимые проблемы
- Введение в анализ алгоритмов
- Трудоемкость алгоритмов и временные оценки
- Теория сложности вычислений и сложностные классы задач
- Пример полного анализа алгоритма решения задачи о сумме
- Рекурсивные функции и алгоритмы
- Рекурсивные алгоритмы и методы их анализа
- Прямой анализ рекурсивного дерева вызовов
Определение трудоемкости алгоритма
Всем привет.
Подскажите пожалуйста трудоемкость цикла while
Существует ли она вообще, прочесывание просторов интернета как-то не дало результатов.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Получить аналитическую оценку трудоемкости работы алгоритма сортировки
есть код программы и нужно вычислить трудоемкость алгоритма, а то какая-то шляпа получилась.
Понятие трудоёмкости алгоритма. Понятие эффективного алгоритма
Понятие трудоёмкости алгоритма. Классификация алгоритмов на основе функции трудоёмкости.
Определение времени работы алгоритма
Помогите надо определить время работы алгоримта Boolean: Function (integer: array) for i=0 to.
Определение алгоритма оптимальной игры
Всем привет! Задача на динамическое программирование, думаю что получится сделать, только вот.
999 / 1848 / 176
Регистрация: 07.05.2013
Сообщений: 3,860
Записей в блоге: 12
Сообщение было отмечено LoliMou как решение
Решение
Не существует. Для итерационных циклов бывает возможно иногда грубо оценить сложность для худшего случая. Но для этого нужно знать — а что там внутри крутится. И вообще, цикл может оказаться просто бесконечным.
Более того, есть алгоритмы, для которых временная сложность в принципе не определяется.
Добавлено через 6 минут
Вот ведь, из памяти вылетело. Долго вспоминал.
Регистрация: 23.10.2018
Сообщений: 3
Вот например, у меня есть алгоритм (фото ниже)
По идее должно же быть 1 + 1 + . (здесь while)*5
Но откуда логарифм в ответе я никак не могу понять
999 / 1848 / 176
Регистрация: 07.05.2013
Сообщений: 3,860
Записей в блоге: 12
Я ввел Вас в заблуждение, потому что сам подумал, что речь идет о временной сложности. Прошу прощенья.
Вот определения из учебника:
Трудоемкость алгоритма – это количество элементарных операций, которые учитываются при анализе алгоритма.
Временная сложность алгоритма – это асимптотическая оценка функции трудоемкости алгоритма для худшего случая.
Таким образом, трудоемкость цикла while равна ( трудоемкость предусловия + трудоемкость тела цикла ) * количество итераций цикла.
В приведенном примере в ответе явная ошибка. Правильный ответ — 5 * log2( n ) + 2
Две операции перед циклом + ( 1 операция сравнения в предусловии + 1 операция умножения + 1 операция записи в переменную + 1 операция сложения + 1 операция записи в переменную ) * количество итераций цикла.
отсюда — 2 + ( 1 + 1 + 1 + 1 + 1 ) * log2( n )