Asymptotic and Computational Complexity of Algorithms and Program Performance
Бесплатный доступ
The paper considers software performance optimization technologies. It examines algorithm characteristics (asymptotic complexity and computational complexity) and the performance of algorithms implemented as programs. Profiling technology is used to optimize program performance. The given description of modern computing architectures shows that a processor and RAM resources cannot be fully taken into account when analyzing using asymptotic and computational complexity. Several examples demonstrate the limited possibilities of optimization using asymptotic and computational complexity. For the given examples, it is shown that using information about the capabilities of the architecture on which the program is executed allows for performance optimization without using low-level commands. Computational experiments were conducted on x86-64 (Intel Core) and ARM (Apple M1) platforms. The paper proposes a methodology for optimizing the performance of developed programs.
Asymptotic complexity, computational complexity, central processor, random access memory, performance, computing platform
Короткий адрес: https://sciup.org/147252419
IDR: 147252419 | УДК: 004.932.72’1 | DOI: 10.14529/mmp250410
Асимптотическая и вычислительная сложность алгоритмов и быстродействие программ
В статье рассматриваются технологии оптимизации производительности программного обеспечения. Изучаются характеристики алгоритмов (асимптотическая сложность и вычислительная сложность), а также производительность алгоритмов, реализованных в виде программ. Для оптимизации производительности программ используется технология профилирования. Приведенное описание современных вычислительных архитектур показывает, что ресурсы процессора и оперативной памяти не могут быть в полной мере учтены при анализе с использованием асимптотической и вычислительной сложности. Приведено несколько примеров, демонстрирующих ограниченные возможности оптимизации с использованием асимптотической и вычислительной сложности. На приведенных примерах показано, что использование информации о возможностях архитектуры, на которой выполняется программа, позволяет оптимизировать производительность без использования низкоуровневых команд. Вычислительные эксперименты проводились на платформах x86-64 (Intel Core) и ARM (Apple M1). Предложена методология оптимизации программ.
