Modeling and Information System in Economics
ISSN 2708-9746
Про деякі аспекти асимптотичного оцінювання складності обчислювальних алгоритмів
About some aspects of asymptotic complexity assessment of computing algorithms
DOI:
10.33111/mise.103.15
Анотація: Асимптотична оцінка математичних функцій є методом спрощеного опису визначення граничних значень їх поведінки. Для оцінки кількості ітерацій або кроків виконання алгоритмів найчастіше використовують наближену оцінку верхньої межі значень відповідних характеристик алгоритмів. У даній публікації пропонується розглянути процес аналітичного визначення мажорант за зміненою схемою. Застосування зазначеної схеми дасть змогу підвищити точність та обґрунтованість аналітичної форми визначених мажорант. Для опису математичного апарату асимптотичної оцінки складності обчислювальних алгоритмів запропоновано систему з однієї леми та дванадцяти теорем. Як приклад застосування проведено асимптотичну оцінку складності деяких обчислювальних алгоритмів. У статті визначено лему про наявність багатьох мажорант, теорему про складність постійного обчислення, теорему про ступінь залежності складності обчислення, теорему про додавання константи до числа обчислень, теорема про кратність трудомісткості обчислень, теорема про транзитивність трудомісткості обчислень, теорема про додавання обсягів обчислень, теорема про додавання обчислювальної трудомісткості, теорема про додавання постійної обчислювальної складності, теорема про множення обчислювальної складності, теорема про поліноміальну обчислювальну складність, теорема про експоненціально-поліноміальну обчислювальну складність, теорема про логарифмічну обчислювальну складність. Розглянутий матеріал наочно демонструє практичні особливості визначення мажорант за зміненою схемою та показує його практичне значення. Наведені приклади визначення обчислювальної складності одних відомих алгоритмів можуть бути покладені в основу визначення обчислювальної складності інших алгоритмів. Крім того, наведену систему теорем можна розширити та застосувати для оцінки комплексного застосування алгоритмів, які доповнюють або є частинами один одного
Abstract: Asymptotic evaluation of mathematical functions is a method of simplified description of determining the limit values of their behavior. To estimate the number of iterations or steps of execution of algorithms, an approximate estimation of the upper limit of the values of the corresponding characteristics of the algorithms is most often used. In this publication, it is proposed to consider the process of analytical determination of majorants according to the changed scheme. The application of the specified scheme will make it possible to increase the accuracy and justification of the analytical form of the determined majorants. A system of one lemma and twelve theorems is proposed to describe the mathematical apparatus for asymptotic assessment of the complexity of computational algorithms. As an example of application, an asymptotic assessment of the complexity of some computational algorithms was performed. the article defines the lemma on the presence of many majorants, the theorem on the complexity of a constant calculation, the theorem on the degree dependence of the complexity of a calculation, the theorem on the addition of a constant to the number of calculations, the theorem on the multiplicity of the complexity of calculations, the theorem on the transitivity of the complexity of calculations, the theorem on the addition of the volumes of calculations, the theorem on addition of calculation complexity, theorem on addition of constant calculation complexity, theorem on multiplication of calculation complexity, theorem on polynomial calculation complexity, theorem on exponential-polynomial calculation complexity, theorem on logarithmic calculation complexity. The considered material clearly demonstrates the practical features of determining majorants according to the changed scheme and shows its practical significance. The given examples of determining the computational complexity of some known algorithms can be used as a basis for determining the computational complexity of other algorithms. In addition, the given system of theorems can be extended and applied to evaluate the complex application of algorithms that complement or are parts of each other.
Ключові слова: Асимптотична оцінка, складність алгоритму, мажоранта, синтез алгоритм
Key words: Asymptotic evaluation, complexity of the algorithm, majorant, synthesis of algorithms.
УДК: 004.42, 330.4
UDC: 004.42, 330.4
To cite paper
In APA style
Potapenko, S. (2023). About some aspects of asymptotic complexity assessment of computing algorithms. Modeling and Information System in Economics, 103, 177-187. http://doi.org/10.33111/mise.103.15
In MON style
Потапенко С.Д. Про деякі аспекти асимптотичного оцінювання складності обчислювальних алгоритмів. Моделювання та інформаційні системи в економіці. 2023. № 103. С. 177-187. http://doi.org/10.33111/mise.103.15 (дата звернення: 11.04.2025).
With transliteration
Potapenko, S. (2023) Pro deiaki aspekty asymptotychnoho otsiniuvannia skladnosti obchysliuvalnykh alhorytmiv [About some aspects of asymptotic complexity assessment of computing algorithms]. Modeling and Information System in Economics, no. 103. pp. 177-187. http://doi.org/10.33111/mise.103.15 [in Ukrainian] (accessed 11 Apr 2025).
# 103 / 2023
Download Paper
100
Views
31
Downloads
0
Cited by
- Borodkina I. L., Borodkin H. O. Teoriia alhorytmiv. — Kyiv: Tsentr uchbovoi literatury, 2021. — 184 s.
- Matviienko M. P. Teoriia alhorytmiv. — Kyiv: Vydavnytstvo Lira-K, 2022. — 340 s.
- Provotar O.I. Konkretna alhorytmika. Kyiv. Naukova dumka. 2017. 168 s.
- Trotsko V. V. Teoriia alhorytmiv: Navchalno. — Kyiv: Universytet ekonomiky ta prava «KROK», 2023. — 123 s.
- Shkilniak S. S. Matematychna lohika, osnovy teorii alhorytmiv. — Kyiv: DP «Vyd. dim «Personal», 2009. — 280 s.
- Bachmann P. Die analytische zahlentheorie. — Leipzig: B. G. Teubner, 1894. — 494 p.
- Landau E. Handbuch der Lehre von der Verteilung der Primzahlen. — Leipzig: B. G. Teubner, 1909. — 564 p.