Page 206 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 206
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
órdeNeS de crecIMIeNto
Las notaciones que normalmente describen el tiempo de ejecución asintótico de un algoritmo son
definidas en términos de funciones cuyos dominios son el conjunto de número naturales .
Tales notaciones son convenientes para describir el peor caso de tiempo de ejecución t (n), el cual
usualmente está definido solamente en entradas de enteros. Se utilizará la notación asintótica prin-
cipalmente para describir los tiempos de ejecución de los algoritmos. La notación asintótica implica
funciones.
El orden de crecimiento del tiempo de ejecución de un algoritmo da una caracterización de la eficien-
cia del algoritmo y nos permite comparar el desempeño relativo de algoritmos alternativos. Cuando
buscamos tamaños de entradas lo suficientemente grandes para obtener el orden de crecimiento
del tiempo de ejecución relevante, entonces estamos estudiando la eficiencia asintótica de los algo-
ritmos. Esto es, nos importa conocer cómo el tiempo de ejecución de un algoritmo aumenta con el
tamaño de la entrada, conforme el tamaño de la entrada aumenta sin ninguna cota o límite. Usual-
mente, un algoritmo que es asintóticamente más eficiente será la mejor opción para todo excepto
para entradas muy pequeñas.
En la siguiente sección se ofrecen varias definiciones de notación asintótica, se presentan diversas
convenciones de notación y el comportamiento de funciones que comúnmente aparecen en el aná-
lisis de algoritmos.
NotacIóN aSINtótIca
La notación que se emplea para describir el tiempo de ejecución asintótica de un algoritmo está
definida en términos de funciones cuyo dominio y contradominio son los números naturales y los
números reales respectivamente. Tal notación es conveniente para describir el tiempo de ejecu-
ción como una función t (n), el cual esta usualmente definida por tamaños de entrada de tipo entero.
Se puede extender la notación en el dominio de números reales o restringirlo a un subconjunto de
números naturales. Sin embargo, hay que asegurarse del significado preciso de la notación para
cuando se haga “mal uso” de la notación.
200
