24. Вычислительная и емкостная сложность алгоритма
Физическое время реализации алгоритма при некотором наборе входных данных может быть определено как 
, где 
— количество операций i-ого типа, 
— время выполнения операции i-го типа, n – количество типов операций. Для одного и того же алгоритма при заданном наборе входных данных время t зависит от языка программирования и быстродействия конкретной ЭВМ. Если мы имеем такую оценку для нескольких алгоритмов решения одной и той же задачи, реализованных на разных языках и предназначенных для выполнения на ЭВМ с различным быстродействием, очевидно, что объективный выбор алгоритма выполнить невозможно. Можно принять за эталон некоторую операцию и, зная отношение времени выполнения i-й операции ко времени выполнения эталонной, можно определить суммарное число эталонных операций:
. Коэффициенты 
можно трактовать как относительное количество тактов 
. Объективная мера временной сложности алгоритма должна быть машинно- и программно-независимой. В качестве такой меры может выступать 
или 
.
, где 
— отношение количества тактов выполнения i-й операции к количеству тактов выполнения эталонной; 
— количество тактов выполнения алгоритма при заданном наборе входных данных.
В зависимости от существующей на данной стадии разработки алгоритма его детализации аналогичной по смыслу с 
и 
оценкой может быть суммарное количество некоторых доминирующих операций или основных действий или шагов. Однако все эти оценки являются некоторой скалярной величиной, так как определяются для заданного набора входных данных. Очевидно, что для входных данных, имеющих другой размер, они будут отличаться. Размер входа задачи может быть как скаляром, так и вектором.
Временная и вычислительная сложность являются функцией от размера входа. Размер входа – скаляр, если количество, например, некоторых действий или шагов зависит только от одного параметра входа задачи. Например, в задачах на графах – только от количества вершин или рёбер. Размер входа – вектор, если от нескольких: для графов – количество вершин, рёбер, локальной степени вершин и т. д.
Понятие вычислительной сложности
Пусть A – алгоритм решения некоторого класса задач, а n – размерность задачи этого класса, тогда вычислительная сложность алгоритма – это некоторая функция 
, отображающая размерность задачи в «математическое» время ее решения, то есть дающая оценку количества некоторых операций, необходимых для решения данным алгоритмом любой задачи данного класса как функции от n. Функция fA(n) является критерием качества алгоритма с точки зрения возможных временных затрат. Эффективным является понятие полиномиальный алгоритм, у которого 
растет не быстрее, чем полином от n. Алгоритм, имеющий экспоненциальную сложность: 
, пригоден для решения задач ограниченной размерности. Такие задачи определяют принадлежащими к классу NP – non-polynomial.
Вычислительная сложность, так же как и погрешность, может иметь оценку в лучшем и в худшем. Оценка в худшем (сверху) получается в том случае, если входные данные являются худшими из возможных. Например, для задачи на графах, предположение, что граф – полный.
Улучшение верхней границы означает нахождение алгоритма с лучшей характеристикой в худшем. Как правило, это обеспечивает использование другого метода или других операций преобразования графа, либо специфических приемов снижения вычислительной сложности, направленных на оптимизацию алгоритма.
Однако ориентация на худший случай нередко приводит к пессимистическим оценкам, которые могут привести к неправильному выбору используемого алгоритма. Более реалистичной является оценка в среднем. Для задач на графы такая оценка появляется при предположении, что граф – однородный с некоторой средней степенью вершин.
Емкостная сложность алгоритма
Емкостная сложность характеризует объем памяти, который необходим для реализации алгоритма. В общем случае объем, который для этого необходим, включает в себя память, требуемую для программы, исходных данных, а также промежуточных и конечных результатов.
При разработке алгоритма оцениваются последние три составляющие. Единица измерения может быть как общепринятая, так и некоторая условная. Оценка емкостной сложности – простая задача, хотя, в ряде случаев, может быть достаточно трудоемкой. При использовании сложных иерархических структур данных задача выбора размеров указателей и прочих компонентов может быть достаточно сложной.
Вычислительная и ёмкостная сложность скоррелированы: как правило, снижение вычислительной сложности достигается за счёт увеличения ёмкостной и наоборот. В качестве обобщенной характеристики сложности алгоритма было предложено использовать так называемый коэффициент сложности 
, где N – суммарное количество эталонных (или доминирующих) операций, V – общий объем памяти.
Временная и емкостная сложность алгоритмов
В данном разделе рассмотрим две характеристики сложности алгоритмов — временная и емкостная. Единицы измерения сложности будем привязывать к классу архитектур наиболее распространенных ЭВМ. Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством скалярных переменных, элементов массивов, элементов записей или просто количеством байт.
Одно из свойств алгоритма — массовость. В общем случае количество операций и требуемая память зависят от исходных данных, т.е. являются функциями вектора X = (х1, х2, . хn) исходных данных. С точки зрения математического анализа сложности, сравнения алгоритмов, их классификации хотелось бы, чтобы функции сложности (x1, x2, . xn) выражались в виде формул с использованием обычных, элементарных математических функций. Тогда оказался бы доступнымбогатый арсенал средств классической математики. Но это не всегда возможно, так как исходные данные могут быть нечисловыми (графы, географические карты, строки символов, звуки и т. д.). Поэтому сложность алгоритма рассматривается как функция от некоторого интегрированного числового параметра V, характеризующего исходные данные. Обозначим: T(V) — временная сложность алгоритма ; S(V) — емкостная сложность. Параметр V, характеризующий данные, называют иногда объемом данных или сложностью данных. Оба эти термина не совсем точны. Выбор параметра V зависит не только от вида данных, но и от вида алгоритма или от задачи, которую этот алгоритм решает. Рассмотрим два примера.
Отыскание функций сложности алгоритмов важно как с прикладной, так и с теоретической точек зрения. В практике проектирования систем реального времени задача разработки программы формулируется так: отыскать такой алгоритм a, решающий задачу P, что Т(X) < Tmax при X D, где D — область допустимых значений входных данных (задача с ограничением на временную сложность). В системах, где критерий качества связан с временем ожидания реакции компьютера (системы управления базами данных, системы автоматического перевода для естественных языков программы для игры в шахматы и другие) задача может быть поставлена так: отыскать среди всех алгоритмов, решающих задачу Р, такой алгоритм а, для которого функция T(X) будет принимать минимальные значения на выбранном подмножестве S значений исходных данных, XSD (задача минимизации временной сложности; дополнительно формулируются ограничения по емкостной сложности).
Двойственная задача минимизации емкостной сложности при ограничениях на временную сложность возникает реже в силу архитектурных особенностей современных ЭВМ, поскольку запоминающие устройства разных уровней, входящие в состав машины, построены так, что программе может быть доступна очень большая, практически неограниченная область памяти — виртуальная память. Недостаточное количество основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Так как в любой момент времени программа работает лишь с двумя-тремя значениями и использование кэша и аппаратного просмотра команд программы вперед позволяет заблаговременно перенести с диска в основную память нужные значения, то можно констатировать, что минимизация емкостной сложности не является первоочередной задачей.
Как определить емкостную сложность
Бесплатный курс по пентесту от Школы Кодебай
Запишись на вводный видеокурс по пентесту , состоящий из 24 уроков. Разные инструменты, тактики и навыки: сканирование сети, фаззинг, брутфорс, сниффинг, sql-инъекции, mimikatz, загрузка полезной нагрузки, эксплуатация разных уязвимостей, XSS, CSRF и немного Reverse-shell. Будет полезен для быстрой подготовки к CTF, а так же для прохождения курсов « SQL Injection Master » и « WAPT ».
Бесплатный курс SQL Injection от Школы Кодебай
Запишись на вводный курс по SQL инъекциям. Курс состоит из 6 видео уроков. К каждому уроку приложена методичка. Есть общий чат для учащихся. Будет полезен для быстрой подготовки к CTF, а так же для прохождения курсов « SQL Injection Master » и « WAPT ».
КАК ПОСЧИТАТЬ ЁМКОСТНУЮ СЛОЖНОСТЬ?
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
14 ответов
Originally posted by OOMPH
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
Ну во-первых.Я не знаю какую именно ёмкостную сложность тебе сказали вычислить, бывают разные типы, зависящие от выбора едениц, а также критериев подсчёта. Самый простой вариант выглядит так : пусть переменная (числовая) занимает C байт (можно взять,конечно, конкретные велечины для int float итд, ведь они известны) , тогда максимальная ёмкостная сложность программы будет равна числу байт(едениц), которое занимают все переменные (n*C), а также + некоторому числу Z = max < exp1,exp2,exp3>; где exp 1. n — это выражения. Пример:
y = 2 + 1; // занимает такое выражение 2 у.е. памяти (допускаем, что число едениц памяти равно числу переменных). Ну, вот считаешь для всех выражений, находишь этот максимум, прибавляешь к памяти переменных. Затем если у тебя есть структуры — там аналогично. Если есть функции — тоже аналогично, плюс ещё память для каждого аргумента функции. Самый грубый подсчёт выглядит именно так, а вообще -то каждый препод по-своему любит, проверено 🙂