Notacion asintotica.

3.3. Notación asintótica
La aplicación más corriente de nuestros cálculos sobre recurrencias es la estimación
del tiempo que un algoritmo tarda en ejecutarse. En tal estimación, no es precisoobtener un resultado numéricamente exacto: lo único de interés es una idea vaga de
cómo aumenta el tiempo de ejecución cuando la dimensión del problema aumenta.
Por ejemplo, los algoritmos usuales parala suma de matrices cuadradas de dimensión
n£n requieren realizar n2 sumas. Si se trata de un producto de matrices, es preciso
multiplicar escalarmente cada fila del primer factor por cada columnadel segundo. Un
producto escalar de un vector de n elementos exige n multiplicaciones y n ¡ 1 sumas,
de forma que el tiempo de ejecución de una multiplicación de dos matrices n £ n es el
60requerido para n2 sumas y n3 ¡ n2 multiplicaciones. La multiplicación suele dominar
en coste a la suma, y está claro que, para matrices de un tamaño moderado, el sumando
n2 es despreciable respecto a n3.De esta forma, adquiere sentido la afirmación “el
producto de matrices consume un tiempo proporcional a n3”.
Este tipo de valoración en que despreciamos todos los términos involucrados en un
cálculosalvo aquéllos cuyo crecimiento domina al de todos los restantes, es lo que se
denomina asintótica. La notación más habitual para expresar estas manipulaciones es
la notación O (léase “O mayúscula”u “O grande”).
* La notación asintótica nos permite realizar simplificaciones sustanciales aun cuando estemos interesados en medir algo más tangible que el tiempo de ejecución, tal como es elnúmero de veces que se ejecuta una instrucción dentro del programa.
* Se denomina notación asintótica porque trata acerca del comportamiento de funciones en el límite, esto quiere decir, para valoressuficientemente grandes de su parámetro. Esto hace que los valores pequeños de las entradas no sean interesantes.
Dicho de otra manera, estamos interesados en las tasas de crecimientos en lugar de...