Automating the analysis of computational and space complexity of the algorithms on the sets and graphs
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.