Программирование

Asymptotic and computational complexity of algorithms and program performance

[Асимптотическая и вычислительная сложность алгоритмов и быстродействие программ]

O. A. Slavin

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Moscow, Russian Federation, oslavin@isa.ru

Аннотация: В статье рассматриваются технологии оптимизации производительности программного обеспечения. Изучаются характеристики алгоритмов (асимптотическая сложность и вычислительная сложность), а также производительность алгоритмов, реализованных в виде программ. Для оптимизации производительности программ используется технология профилирования. Приведенное описание современных вычислительных архитектур показывает, что ресурсы процессора и оперативной памяти не могут быть в полной мере учтены при анализе с использованием асимптотической и вычислительной сложности. Приведено несколько примеров, демонстрирующих ограниченные возможности оптимизации с использованием асимптотической и вычислительной сложности. На приведенных примерах показано, что использование информации о возможностях архитектуры, на которой выполняется программа, позволяет оптимизировать производительность без использования низкоуровневых команд. Вычислительные эксперименты проводились на платформах x86-64 (Intel Core) и ARM (Apple M1). Предложена методология оптимизации программ.

Ключевые слова: асимптотическая сложность, вычислительная сложность, ускорение, вычислительная платформа.

УДК: 004.932.72'1

MSC: 90C35, 90C27

Поступила в редакцию: 10.07.2025

Язык публикации: английский

DOI: 10.14529/mmp250410