Cálculo automático de la eficiencia asintótica de programas imperativos

Autores: Xavier Franch , Joan Vancells
Localización: III Jornadas de Informática. Actas: El Puerto de Santa María (Cádiz), 14 al 18 de julio 1.997 [sic] / Juan Carlos Torres Cantero (dir. congr.) , 1997, ISBN 84-8498-463-X, págs. 383-392
Idioma: español
Texto completo no disponible (Saber más ...)
Resumen
- Se presenta en este artículo una propuesta para el cálculo automático del tiempo de ejecución de los programas imperativos, medido con la nota asintótica O grande , y considerando el peor de los casos en el comportamiento de los programas. Para ello, se propone tratar el tiempo de ejecución como un atributo sintetizado de la gramática, y damos las reglas de cálculo adecuadas para un lenguaje de trabajo representativo del paradigma imperativo, destacando la eventual necesidad de definir reglas parametrizadas y de añadir en los programas información relativa a la eficiencia. Se intorduce asimismo el concepto de esqueleto para especificar patrones de combinación de operaciones con una eficiencia potencialmente diferente de la que se calcularía con las reglas estándar. Los resultados de la eficiencia se ofrecen simplificados al máximo gracias a la aplicación de unas propiedades de los operadores de la notación O.