Bienvenida

Programacion II

Medidas asintóticas y órdenes de complejidad

Entre las personas que comienzan el estudio de PROGRAMACION II siguiendo el texto recomendado ("Diseño de Programas" de Ricardo Peña Marí), uno de los primeros traumas suele provocarlo la definición:

Este tipo de definiciones hace que muchas personas que habían decidido sacrificar su vida dedicándose a la ingeniería práctica, la que resuelve problemas, decidan que el esfuerzo no merece la pena. Espero que esta cita ayude a reintegrarlos al redil:

"Si no fuera por las compulsiones de los ingenieros, la humanidad nunca hubiera llegado a conocer la rueda, y se habría conformado con el trapezoide porque algún neandertal especialista en marketing habría convencido a todo el mundo que tenía una mayor capacidad de frenada que la rueda".

Scott Adams, "El principio de Dilbert"

Consideremos pues, que a alguien le ha de tocar sacrificarse por el bien de la humanidad y volvamos a lo nuestro. Como ya se ha indicado anteriormente, las matemáticas son para el ingeniero un medio de comunicación rápida y precisa con los de su especie (ingenieros, físicos y demás gente del gremio). Para que esa comunicación sea efectiva se han de tener la capacidad de entender los conceptos prácticos que se esconden tras una definición abstracta o una ecuación. En este apartado se intentará "diseccionar" la definición anterior de forma que se traduzca a conceptos prácticos. En todo caso se ha de considerar que para abordar el estudio de Programación II es conveniente repasar, o abordar el estudio, de algunos conceptos matemáticos. Para el estudio de medidas asintóticas el concepto de límite matemático de funciones y sucesiones y los métodos de cálculo de límites son herramientas necesarias que pueden repasarse en cualquier texto de Análisis Matemático.

Como ya se ha indicado en el apartado previo cuando se analiza el coste asintótico, en cuanto a tiempo de ejecución, lo que interesa es ver COMO CRECE el tiempo al crecer el tamaño del problema. Consideremos varios algoritmos (f1,f2, f3 ) cuyo tamaño de problema depende de un parámetro n y cuyo tiempo de ejecución se presenta, para distintos valores de n, en la siguiente tabla. En la misma tabla se representa la función f(n)=n².

Si se observa cómo crece el coste para valores altos de n. En concreto cuando n se multiplica por 10 se tiene:

• f1 se multiplica por 100 (10²) aproximadamente.

• f2 se multiplica por 1000 (10³) aproximadamente.

• f3 se multiplica por 10 (10¹).

Luego f1 tiene un crecimiento de tipo cuadrático, f2 de tipo cúbico y f3 de tipo lineal. Si se considera, por ejemplo, la función f(n)=n² se pueden definir tres conjuntos de funciones basados en f :

• El conjunto de las funciones que crecen asintóticamente de forma igual o menos rápida que n², este conjunto (infinito en este caso) de funciones se denota por

• El conjunto de las funciones que crecen asintóticamente de forma igual o más rápida que n² este conjunto (infinito en este caso) de funciones se denota por

• El conjunto de las funciones que crecen asintóticamente de forma igual a n² este conjunto (infinito en este caso) de funciones se denota por

Es evidente que es la intersección de los conjuntos y. En el ejemplo de la tabla se tiene que f1 pertenece a y también a y aya que crece de forma cuadrática. f2 pertenece sólo a ya que crece de forma cúbica, es decir más rápidamente que n² . f3 pertenece sólo a ya que crece de forma lineal. Es decir más lentamente que n² .

En general, se utilizará el orden de tipo , ya que se trata de buscar una cota superior al crecimiento del coste del algoritmo. También se utiliza frecuentemente el tipo que permite conocer el coste asintótico exacto del algoritmo.

Sabiendo que, en realidad, las funciones f1, f2 y f3 están definidas por:

f1=0,01n²+ 80

f2=0,1n³+n

f3=5n, en la tabla siguiente se ha calculado el cociente entre los valores que toman las funciones f1,f2 y f3, respectivamente y el valor que toma n² para distintos valores de n.

Puede observarse que, cuando n tiende a infinito:

• f1/n² tiende a un valor constante (0,010).

• f2/n² crece indefinidamente, es decir, tiende a infinito

• f3/n² decrece indefinidamente, es decir, tiende a cero.

Se han presentado con un ejemplo las condiciones suficientes que permiten determinar cuando una función cualquiera g(n) es del orden (de los distintos tipos de orden) de otra dada f(n) (en el ejemplo f(n)=n² ). Algunas de estas condiciones son:

Propiedad 1

O sea, g(n) crece "más despacio" que f(n).

Propiedad 2

O sea, g(n) crece "al mismo ritmo" que f(n)

Propiedad 3

O sea g(n) crece "más deprisa" que f(n)

Normalmente se trata de buscar una función sencilla f(n) que acote superiormente el crecimiento de otra g(n). Para ello es conveniente tener en cuenta una regla que se obtiene al combinar las propiedades 1 y 2 anteriores:

Propiedad 4

Para el ejemplo tratado, si se trata de ver si las funciones f1, f2 y f3 son, respectivamente, de orden cuadrático, es decir si pertenecen a se tendrá:

• que f1 pertenece a , puesto que el límite cuando n tiende a infinito del cociente de f1 entre n² es una constante (0,010)

• que f2 no pertence a , puesto que ahora el límite es infinito

• que f3 si pertenece a , puesto que ahora el límite es cero.

Si lo que se desea es conocer si alguna de las funciones es de orden cuadrático exacto, es decir, si pertenece a entonces el límite ha de ser una constante positiva no nula, y por tanto, la única función de orden cuadrático exacto es f1.

Y ahora, una explicación que permita entender mejor la definición 1.1 expuesta al principio de esta página, decir que:

es equivalente a decir que

o lo que es lo mismo:

Se puede encontrar un número real k no negativo y un número natural n₀ , tales que para todo número natural n>n₀ es g(n)<=k.f(n). Esto es lo que indica la definición 1.1, si bien de una forma más general ya que esta definición puede aplicarse incluso en casos en los que los límites no existen (el ejercicio 1.2 de Peña 1ª Ed expone un ejemplo):

Expresado en palabras: Dada una función de un parámetro n, natural y que toma valores no negativos, se puede definir un conjunto (normalmente infinito) de funciones, que se define como el conjunto de funciones del orden de dicha función. Este conjunto está formado por todas las funciones para las que es posible encontrar una constante real positiva c, y un número natural n₀ tal que para todos los números naturales mayores que n₀ se cumple que dicha función no supera en valor a c.f(n). La constante c y el número natural n₀ deberá particularizarse, en general, para cada una de las funciones.

Definiciones análogas se tienen (ver texto de Peña) para los otros tipos de orden.

La mejor forma de acabar de entender estos conceptos es revisando ejemplos: ejer03.pdf

Ir a origen de página