Cotas asintóticas de coste

Abstract

La complejidad asintótica de un programa describe la escalabilidad de su coste de ejecución. Observa su comportamiento cuando procesa datos arbitrariamente grandes y considera semejantes dos programas cuyos costes crecen de manera similar. Existen algunos analizadores automáticos de coste que, cuando se emplean para procesar programas reales, generan funciones no asintóticas de coste demasiado complejas para su uso práctico. En este trabajo desarrollamos e implementamos un algoritmo capaz de simpli- ficar esas funciones a su forma asintótica, más compacta y manejable.Hemos integrado dicho algoritmo en un resolutor de ecuaciones, capaz de generar directamente funciones asintóticas sin necesidad de calcular las no asintóticas; lo que en nuestras pruebas experimentales ha resultado ser más eficaz. Ello permite mejorar la escalabilidad de los analizadores de coste, un aspecto crucial para su uso industrial. [ABSTRACT] Asymptotic complexity analysis is used for describing programs' excution cost scalability, by observing its behaviour when processing large input data and considering as equivalent two programs whose costs grow at the same rate. There are non-asymptotic cost analyzers which, when used over realistic programs, provide complex non-asymptotic cost functions that can't be used in some practical applications. That's why we have developed an algorithm that simplifies a cost function to its asymptotic form, more compact and manageable. We have integrated that algorithm into a cost analyzer, and now it generates asymptotic functions without having to firstly compute their non-asymptotic counterparts, a process that our experiments show to be more effcient. This allows us to improve cost analyzers' scalability, a concerning issue for its application in software industry.