Определение трудоемкости алгоритма
Всем привет.
Подскажите пожалуйста трудоемкость цикла while
Существует ли она вообще, прочесывание просторов интернета как-то не дало результатов.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Получить аналитическую оценку трудоемкости работы алгоритма сортировки
есть код программы и нужно вычислить трудоемкость алгоритма, а то какая-то шляпа получилась.
Понятие трудоёмкости алгоритма. Понятие эффективного алгоритма
Понятие трудоёмкости алгоритма. Классификация алгоритмов на основе функции трудоёмкости.
Определение времени работы алгоритма
Помогите надо определить время работы алгоримта Boolean: Function (integer: array) for i=0 to.
Определение алгоритма оптимальной игры
Всем привет! Задача на динамическое программирование, думаю что получится сделать, только вот.
984 / 1770 / 171
Регистрация: 07.05.2013
Сообщений: 3,783
Записей в блоге: 12
Сообщение было отмечено LoliMou как решение
Решение
Не существует. Для итерационных циклов бывает возможно иногда грубо оценить сложность для худшего случая. Но для этого нужно знать — а что там внутри крутится. И вообще, цикл может оказаться просто бесконечным.
Более того, есть алгоритмы, для которых временная сложность в принципе не определяется.
Добавлено через 6 минут
Вот ведь, из памяти вылетело. Долго вспоминал.
Регистрация: 23.10.2018
Сообщений: 3
Вот например, у меня есть алгоритм (фото ниже)
По идее должно же быть 1 + 1 + . (здесь while)*5
Но откуда логарифм в ответе я никак не могу понять
984 / 1770 / 171
Регистрация: 07.05.2013
Сообщений: 3,783
Записей в блоге: 12
Я ввел Вас в заблуждение, потому что сам подумал, что речь идет о временной сложности. Прошу прощенья.
Вот определения из учебника:
Трудоемкость алгоритма – это количество элементарных операций, которые учитываются при анализе алгоритма.
Временная сложность алгоритма – это асимптотическая оценка функции трудоемкости алгоритма для худшего случая.
Таким образом, трудоемкость цикла while равна ( трудоемкость предусловия + трудоемкость тела цикла ) * количество итераций цикла.
В приведенном примере в ответе явная ошибка. Правильный ответ — 5 * log2( n ) + 2
Две операции перед циклом + ( 1 операция сравнения в предусловии + 1 операция умножения + 1 операция записи в переменную + 1 операция сложения + 1 операция записи в переменную ) * количество итераций цикла.
отсюда — 2 + ( 1 + 1 + 1 + 1 + 1 ) * log2( n )
§ 23. Понятие правильности и сложности алгоритма
Основным показателем сложности (трудоемкости) алгоритма является время, необходимое для решения задачи, и объем требуемой памяти. Существуют понятия сложности в худшем и среднем случае. Обычно оценивают сложность в худшем случае.
Временная сложность в худшем случае — функция от размера входа, равная максимальному количеству операций, выполненных в ходе работы алгоритма при решении задачи данного размера.
Емкостная сложность в худшем случае — функция от размера входа, равная максимальному количеству памяти, к которому было обращение при решении задач данного размера.
При анализе сложности для класса задач определяется некоторое число, характеризующее объем данных, которое требуется для представления входных данных задачи. Это величина называется размер входа. Можно сделать вывод, что сложность алгоритма — функция размера входа. Размер входа может зависеть как от числа входных данных, так и от величины входных данных (пример 23.1).
Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов различных алгоритмов, предназначенных для решения одной и той же задачи, при больших объемах входных данных.
Используемая в асимптотическом анализе оценка функции трудоемкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоемкость алгоритма с увеличением объема данных.
В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе.
Чтобы определить сверху трудоемкость алгоритма, используется обозначение O, читается «о большое» (пример 23.2).
Иногда при анализе алгоритма приходится учитывать не только максимальное, но и минимальное количество операций, необходимое для решения задачи. В этом случае используется обозначение , читается «омега».
Существует ряд важных практических причин для анализа алгоритмов. Одной из них является необходимость получения оценок или границ для объема памяти, или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память — относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени. Теоретический анализ способен выявить узкие места в программах.
Иногда невозможно составить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, в то время как другой лучше работает на каких-то специальных входных данных.
Будем пользоваться следующим критерием для оценки качества алгоритма: чем медленнее растет функция f(n) на каком-то участке области , тем алгоритм будет более эффективным (пример 23.3).
Этот критерий основан на времени работы в худшем случае, но аналогичный критерий может быть также определен для среднего времени работы.
При разработке алгоритма необходимо стремиться к тому, чтобы рост функции f(n) для алгоритма был как можно медленнее на той области, на которой требуется получить решение. Однако здесь могут возникать определенные трудности.
- Очень часто отдельно взятый шаг алгоритма может быть выражен в форме, которую трудно перевести непосредственно в конструкции языка программирования.
- Конкретная реализация (выбор различных языков программирования и/или различных структур данных) может существенно влиять на требования к памяти и на скорость алгоритма.
Пример 23.1. Оценка сложности поисковых алгоритмов.
Линейный поиск
Нахождение информации в неотсортированной структуре данных, например в массиве, требует применения последовательного поиска. Последовательный поиск в среднем случае выполнит проверку n/2 элементов, а в худшем — элементов. При этом предполагается, что сравнение двух чисел выполняется за 1 операцию.
Бинарный поиск
Этот метод поиска значительно эффективнее, чем последовательный поиск, но требует, чтобы данные были предварительно упорядочены (отсортированы). В худшем случае выполняется не более log2n, в связи с чем метод еще называется логарифмическим поиском.
Пусть n — размер входных данных. Оценка сложности алгоритма f(n) = 0(g(n)), если при g > 0 и n > 0 существуют такие положительные C, n0, что f(n0) ≤ C * g(n0) .
Другими словами, скорость роста функции f при достаточно больших n не выше скорости роста функции g.
Оценка сложности алгоритмов сортировки.
Для метода сортировки обменом оценка трудоемкости составляет — O(n 2 ). Это означает, что количество операций при сортировке элементов не превосходит величину C · n 2 при некотором значении коэффициента C, который не зависит от n.
Для быстрой сортировки оценка трудоемкости составляет в среднем — O(nlog2n). Это означает, что количество операций при сортировке элементов не превосходит величину C · nlog 2 n при некотором значении коэффициента C, который не зависит от n. Оценка в худшем случае такая же, как для сортировки обменом.
Пусть — размер входных данных. Оценка сложности алгоритма
f(n) = (g(n)),
если при g > 0 и n > 0 существуют такие положительные c, n0, что
Другими словами, скорость роста функции f при достаточно больших не ниже скорости роста функции g.
Пример 23.3. Возможные оценки качества алгоритма.
Константный алгоритм — O(1)
Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Важно то, что это время не зависит от входных данных.
Линейный алгоритм — O(n)
Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Если линейный алгоритм обрабатывает один элемент пять миллисекунд, то мы можем ожидать, что тысячу элементов он обработает за пять секунд. Например, линейный поиск.
Логарифмический алгоритм — O(logn)
Порядок роста O(logn) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. При анализе алгоритмов по умолчанию используется логарифм по основанию 2. Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Например, бинарный поиск.
Линейно-логарифмический алгоритм — O (nlogn)
Линейно-логарифмический алгоритм имеет порядок роста O (nlogn) . Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. Например, быстрая сортировка (в среднем) или метод sort в STL.
Квадратичный алгоритм — O(n 2 )
Время работы алгоритма с порядком роста O ( n 2 ) зависит от квадрата размера входных данных. Например, если массив из тысячи элементов потребует 1 000 000 операций, то массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Например, сортировка обменом.
Полиномиальный алгоритм — O ( n k )
О полиномиальной сложности (порядка k) говорят тогда, когда время работы алгоритма растет не быстрее, чем полином k-й степени от n.
Экспоненциальный алгоритм — O(2 n ), O(e n ), O(n n ) и др.
Если время работы алгоритма растет не медленнее, чем экспонента от n , то говорят об экспоненциальном алгоритме.
Анализ трудоёмкости алгоритмов
Целью анализа трудоёмкости алгоритмов является нахождение оптимального алгоритма для решения задачи. В качестве критерия оптимальности алгоритма выбирается трудоемкость алгоритма, понимаемая как количество элементарных операций, которые надо выполнить для решения задачи с помощью данного алгоритма. Функцией трудоемкости называется отношение, связывающие входные данные алгоритма с количеством элементарных операций. Одним из упрощенных видов анализа, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов при использовании различных алгоритмов, предназначенных для решения одной и той же задачи, при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных. Для описания скорости роста функций используется асимптотическая оценка 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 1 0 0 1 16 4 64 256 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) с точностью до постоянного множителя. Асимптотические оценки можно представить в порядке увеличения скорости их роста: O(1) < O(log2 n) < O(n) < O(nlog2 n) < O(n 2 ) < O(n 3 ) < O(2 n )
29.04.2018 198.26 Кб 38 l3.pptx
29.04.2018 124.48 Кб 41 l4.pptx
29.04.2018 824.83 Кб 39 Lk-OAp-5rextrktfyl.doc
29.04.2018 878.59 Кб 38 Lk-OAp-6spsxtoch.doc
29.04.2018 1.41 Mб 39 Lk-OAp-7binderkch.doc
29.04.2018 939.52 Кб 90 Lk-Oap-8kheshsortalg.doc
29.04.2018 463.36 Кб 48 Л 8_ очереди.ppt
29.04.2018 488.19 Кб 43 л5 списки.pptx
29.04.2018 1.24 Mб 48 Лекция 10_Деревья2.ppt
29.04.2018 894.46 Кб 62 Лекция 11 сложность.ppt
29.04.2018 2.3 Mб 47 Лекция 2_Сортировки.ppt
Ограничение
Для продолжения скачивания необходимо пройти капчу:
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):
Таким образом, минимальная и максимальная трудоемкости всего алгоритма равны соответственно: