Как рассчитать ёмкостную сложность алгоритма?
Как я понял, ёмкостная сложность измеряется в байтах. Есть ли в C# возможность посчитать эти байты во время выполнения программы? И можно ли вообще программно рассчитать сложность алгоритма сортировки? Или только посчитать количество циклов и представить в виде О большого?
Отслеживать
задан 22 авг 2022 в 18:00
51 6 6 бронзовых знаков
Можно измерить потребление памяти во время каждого отдельного прогона. Но, ёмкостная сложность — функция, восстановить которую по отдельным прогонам можно только приближенно. Обычно проделывается некоторая теоретическая работа по анализу исходного кода. Результат этой работы — функция в нотации О-большого которая описывает как меняется потребление памяти в зависимости от размера сортируемого массива.
22 авг 2022 в 18:15
0
Сортировка: Сброс на вариант по умолчанию
Знаете кого-то, кто может ответить? Поделитесь ссылкой на этот вопрос по почте, через Твиттер или Facebook.
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.10.27.43697
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Емкостная сложность алгоритмов
Объясните пожалуйста, на простом примере, как вычислять емкостную сложность алгоритмов.
Буду благодарен, спасибо.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public CountSort(int size) { thearray = new int [size] ; Random ran = new Random(); for(int i = 0 ; i size; i++) { thearray[i] = ran.Next(7, 23); } }
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Сложность алгоритмов
Оценить временную сложность алгоритма выбора лучшего хода в русских шашках.
Временная сложность алгоритмов
Сколько времени займет подсчет до 1 миллиарда (не учитывая переполнение)? Определите время работы.
Временная сложность алгоритмов
Здравствуйте! Собственно, задание: даны 2 алгоритма, надо узнать что они выполняют и их временную.
Сложность алгоритмов + паралельные вычисления
Здравствуйте. Возник вопрос касательно сложности алгоритмов. Допустим у нас есть алгоритм.
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
емкостная сложность — это функция, выражающая зависимость требуемой памяти от размера входных данных.
например, вам дан массив и требуется вывести его в отсортированном порядке. если вам дадут сто чисел, то вам понадобится массив из 100 ячеек. если миллион чисел — массив из миллиона ячеек. зависимость необходимой памяти от размера входных данных линейная. поэтому скажем, что емкостная сложность алгоритма, решающего задачу сортировки .
другая задача. надо найти наибольшую общую подстроку двух строк. предположим, вы умеете решать ее только динамикой и ко всему прочему вы еще и не умеете оптимизировать по памяти эту динамику тогда вы будете насчитывать матрицу dp[длина первой строки][длина второй строки]. ну тогда, если обе строки длиной 10, то вам потребуется матрица из 100 ячеек. а если длины 100, то матрица из 10000 ячеек. зависимость уже квадратичная. тогда сложность оценим как .
§ 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 – оценка для худшего случая
Рассмотрим сложность f(n) > 0, функцию того же порядка g(n) > 0, размер входа n > 0.
Если f(n) = O(g(n)) и существуют константы c > 0, n0 > 0, то
0 < f(n) < c*g(n),
для n > n0.
Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).
Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.
Примеры асимптотических функций
| f(n) | g(n) |
|---|---|
| 2n 2 + 7n — 3 | n 2 |
| 98n*ln(n) | n*ln(n) |
| 5n + 2 | n |
| 8 | 1 |
Ω – оценка для лучшего случая
Определение схоже с определением оценки для худшего случая, однако
f(n) = Ω(g(n)), если
0 < c*g(n) < f(n)
Ω(g(n)) определяет класс функций, которые растут не медленнее, чем функция g(n) с точностью до константного множителя.
Θ – оценка для среднего случая
Стоит лишь упомянуть, что в данном случае функция f(n) при n > n0 всюду находится между c1*g(n) и c2*g(n), где c – константный множитель.
Например, при f(n) = n 2 + n; g(n) = n 2 .
Критерии оценки сложности алгоритмов
Равномерный весовой критерий (РВК) предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК) учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти.
Временная сложность при ЛВК определяется значением l(Op), где Op – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M), где M – величина ячейки памяти.
Пример оценки сложности при вычислении факториала
Необходимо проанализировать сложность алгоритма вычисление факториала. Для этого напишем на псевдокоде языка С данную задачу:
void main()
Временная сложность при равномерном весовом критерии
Достаточно просто определить, что размер входа данной задачи – n.
Количество шагов – (n — 1).
Таким образом, временная сложность при РВК равна O(n).
Временная сложность при логарифмическом весовом критерии
В данном пункте следует выделить операции, которые необходимо оценить. Во-первых, это операции сравнения. Во-вторых, операции изменения переменных (сложение, умножение). Операции присваивания не учитываются, так как предполагается, что она происходят мгновенно.
Итак, в данной задаче выделяется три операции:
1) i
На i-м шаге получится log(n).
Так как шагов (n-1), сложность данной операции составит (n-1)*log(n).
2) i = i + 1
На i-м шаге получится log(i).
Таким образом, получается сумма .
3) result = result * i
На i-м шаге получится log((i-1)!).
Таким образом, получается сумма .
Если сложить все получившиеся значения и отбросить слагаемые, которые заведомо растут медленнее с увеличением n, получим конечное выражение .
Ёмкостная сложность при равномерном весовом критерии
Здесь всё просто. Необходимо подсчитать количество переменных. Если в задаче используются массивы, за переменную считается каждая ячейка массива.
Так как количество переменных не зависит от размера входа, сложность будет равна O(1).
Ёмкостная сложность при логарифмическом весовом критерии
В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение Vmax.
В данной задаче существует переменная, значение которой не превосходит n (i), и переменная, значение которой не превышает n! (result). Таким образом, оценка равна O(log(n!)).
Выводы
Изучение сложности алгоритмов довольно увлекательная задача. На данный момент анализ простейших алгоритмов входит в учебные планы технических специальностей (если быть точным, обобщённого направления «Информатика и вычислительная техника»), занимающихся информатикой и прикладной математикой в сфере IT.
На основе сложности выделяются разные классы задач: P, NP, NPC. Но это уже не проблема теории асимптотического анализа алгоритмов.
- теория алгоритмов
- оценка алгоритмов
- алгоритмы
- асимптотический анализ алгоритмов