Asymptotic and Computational Complexity of Algorithms and Program Performance

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

Ключевые слова

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

Литература

1. Slavin O.A. Software Performance Optimization for Classification and Linking of Administrative Documents. Programming and Computer Software, 2024, vol. 50, pp. 457-466. DOI: 10.1134/S0361768824700324
2. Trusov A., Limonova E., Nikolaev D., Arlazarov V.V. 4.6-Bit Quantization for Fast and Accurate Neural Network Inference on CPUs. Mathematics, 2024, vol. 12, no. 5, pp. 651. DOI: 10.3390/math12050651
3. Sher A., Trusov A., Limonova E., Nikolaev D., Arlazarov V.V. Neuron-by-Neuron Quantization for Efficient Low-Bit QNN Training. Mathematics, 2023, vol. 11, no. 9, pp. 2112. DOI: 10.3390/math11092112
4. Williams R. Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM Journal on Computing, 2018, vol. 47, no. 5, pp. 1965-1985. DOI: 10.1137/15M1024524
5. Abboud A., Williams V.V. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 434-443. DOI: 10.1109/FOCS.2014.53
6. Holm J., de Lichtenberg K., Thorup M. Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. Journal of the Association for Computing Machinery, 2001, vol. 48, no. 4, pp. 723-760. DOI: 10.1145/276698.276715
7. Knuth D.E. The Art of Computer Programming. Fundamental Algorithms, Third Edition, 1997, vol. 1.
8. Razborov A. Foundations of Computational Complexity Theory. Surveys in Modern Mathematics, London Mathematical Society Lecture Note Series, 2005, vol. 321, pp. 186-202.
9. Klee V., Minty G.J. How Good is the Simplex Algorithm? Inequalities III, Academic Press, New York, 1972, pp. 159-175.
10. Khachiyan L. A Polynomial Algorithm in Linear Programming. Soviet Mathematics Doklady, 1979, vol. 20, pp. 191-194.
11. Bringmann K. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 661-670. DOI: 10.1109/FOCS.2014.76
12. Alman J., Williams V.V. A Refined Laser Method and Faster Matrix Multiplication. 61st IEEE Symposium on Foundations of Computer Science, 2020. DOI: 10.48550/arXiv.2010.05846
13. Shenmaier V. On the Complexity of the Geometric Median Problem with Outliers. arXiv: Computer Science. Computational Geometry, 2021. DOI: 10.48550/arXiv.2112.00519
14. Woodruff D.P. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 2014, vol. 10, no. 1-2, pp. 1-157. DOI: 10.1561/0400000060
15. Backurs A., Indyk P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). SIAM Journal on Computing, 2018, vol. 47, no. 3, pp. 1087-1097. DOI: 10.1137/15M1053128
16. Egunov V.A., Kravets A.A. The New Method for Automatic Vectorization Efficiency Increasing. Springer. Cyber-Physical Systems: Data Science, Modelling and Software Optimization, 2024, pp. 195-208. DOI: 10.1007/978-3-031-67685-7_14
17. Intel\textsuperscript\textregistered VTune\textsuperscriptTM Profiler Performance Analysis Cookbook, https://www.intel.com/content/www/us/en/docs/vtune-profiler/cookbook/2023-2/overview.html (аccessed on 23.04.2025).
18. Alwan E.H., Ketran R.M., Hussein I.A. A Comprehensive Survey on Loop Unrolling Technique In Code Optimization. Journal of University of Babylon for Pure and Applied Sciences, 2024, vol. 32, no. 1, pp. 108-117. DOI: 10.29196/8cw3s787
19. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
20. Egunov V.A., Kravets A.A. The Method for Increasing the Software Efficiency for Computing Systems with a Hierarchical Memory Structure. Cyber-Physical Systems Engineering and Control: Studies in Systems, Decision and Control, 2023, pp. 221-231. DOI: 10.1007/978-3-031-33159-6_17