Asymptotic and computational complexity of algorithms and program performance

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