Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

Automating the analysis of computational and space complexity of the algorithms on the sets and graphs

Published: 19.11.2013

Authors: Ivanova G.S.

Published in issue: #11(23)/2013

DOI: 10.18698/2308-6033-2013-11-1043

Category: Information technology

A method allowing to obtain automatically estimates of structural algorithms of computing, time and space complexity for solving the problems of structural analysis and synthesis, described in the operations on graphs, and/or sets is offered. The algorithm implements the D-maps method. The input data for the evaluation of computational and time complexity of the algorithm are its model in the operations on graphs and sets, and tables of the operations complexity in the operations of comparison or time units. Algorithms for estimating the time and computational complexity are realized by recursive identification of base and derived algorithm structural constructions using the structural construction invariants, the calculation of the required characteristics of these structures with the proposed in the article relations and recognized structures convolution with respective integral estimates. Evaluation of algorithm capacitive is performed using the model data structures involved.