Вычислительная сложность решения задач автоматизации — это понятие в информатике и теории алгоритмов, которое обозначает функцию зависимости объёма работы, выполняемой определённым алгоритмом, от размера исходных данных.
Вычислительная сложность решения задач автоматизации
Актуальность проблемы понижения вычислительной сложности алгоритмов объясняется постоянным ростом уровня интеграции проектируемых систем, что ведёт к возрастанию размера входа проектных задач. При разработке систем для снижения длительности жизненного цикла формирования продукта повсеместно применяются системы автоматизированного проектирования (САПР), а также уже существующие решения или библиотеки. Использованные в них алгоритмы часто не рассчитывались на существенный рост размера входа задач, что ведёт к неприемлемому возрастанию длительности цикла проектных работ. При создании новых алгоритмов значительные размеры входа задач способны вести к необходимости сокращения уровня детализации объекта проектирования или к применению приближенных методов решения, которые не обеспечивают необходимой точности результата.
Эффективным методом разрешения данной проблемы может стать применение оптимизирующих преобразований как к проектируемым, так и к уже известным алгоритмам. Оптимизирующим преобразованием (или оптимизацией) является замена фрагмента алгоритма на эквивалентный с точки зрения итоговых результатов на одних и тех же входных данных, которая приводит к улучшению качественных показателей алгоритма. В частности, возможно уменьшение размера используемой алгоритмом памяти или сокращение времени его исполнения. Так как память компьютера считается сравнительно недорогим и легко наращиваемым элементом, то больше интересует понижение вычислительной сложности алгоритмов.
Для повсеместного использования методов понижения вычислительной сложности алгоритмов следует их формировать в формате модуля исполнения оптимизирующих преобразований. Для проектирования подобного модуля нужно иметь систематизированное изложение методов снижения вычислительной сложности с оценкой возможности осуществления их автоматизации. Необходимо заметить, что известно очень мало литературных источников, в которых системно описаны методы снижения вычислительной сложности алгоритмов.
Способы сокращения вычислительной сложности
С позиций возможности создания модуля оптимизирующих преобразований они могут быть классифицированы следующим образом:
- Преобразования, которые могут быть автоматизированы.
- Преобразования, которые могут быть автоматизированы в диалоговом режиме.
- Преобразования, которые невозможно автоматизировать.
Под чисто автоматизируемыми следует понимать такие преобразования, которые могут быть полностью описаны при помощи грамматических правил замены. К преобразованиям второго типа могут быть отнесены такие преобразования, которые не могут быть использованы в автоматическом режиме. Однако они или могут быть применены после запроса дополнительной информации у проектировщика, или, наоборот, ему могут быть указаны фрагменты алгоритма, которые, вероятно, необходимо оптимизировать.
В частности, может быть использовано изменение способа представления графа в зависимости от его свойств. При формировании алгоритма проектировщики обычно уделяют большое внимание операциям над данными и существенно меньшее внимание уделяется методу представления графа. Для формализованных преобразований графа можно использовать следующие способы его задания:
- Табличный способ, то есть, задание графа в форме матриц инцидентности или смежности.
- Аналитический способ, то есть, задание графа множествами вершин и ребер, а также их образов и прообразов относительно предикатов инцидентности или смежности.
Каждый из способов имеет свои преимущества и недостатки. Матричное представление позволяет обеспечить получение значения отношения между элементами графа за постоянное время O(1). Но, если граф обладает большой размерностью, то есть большим количеством вершин n, то необходим большой объём памяти $0(n^2)$ для хранения матрицы смежности и O(mn) требуется для хранения матрицы инцидентности, где: m является числом рёбер графа.
В таком случае время информационного обмена способно значительно превысить время исполнения операций над этими информационными данными. На практике может быть использована такая характеристика, как среднее количество рёбер, инцидентных вершине, которое ограничено некоторой константой р. Тогда в среднем количество значимой информации, то есть число «1» в матрице инцидентности, будет равняться рп, а коэффициент использования матрицы соответственно:
$K = (pn)/(mn) = р/m$
Но поскольку в реальных задачах р ∠∠т, то, следовательно, это означает, что память используется очень неэффективно. В случае, если требуется осуществлять действия с насыщенным графом, то применение матричной структуры является оправданным.
Представление при помощи образов и прообразов предполагает применение более сложной структуры данных, а именно, вектора списков или списка списков. Оно считается более экономным в сравнении с матричным, так как способно занимать память пропорционально объёму полезной информации. Однако в насыщенном графе накладные расходы на применение подобных структур данных очень немалые. В частности, для списковой структуры необходимо сохранять указатели на следующий и предыдущий элементы, в то время как для матрицы необходим лишь адрес базы.
Таким образом, когда граф является разреженным, то более эффективно его отображать в аналитическом виде, а когда граф является насыщенным, то лучше его представлять в форме матриц смежности или инцидентности. Тем не менее известны частные случаи, к примеру, при небольшой размерности графа, когда затраты на хранение «0» в матрице меньше накладных расходов на хранение более сложной структуры данных.
