Tiempo de ejecución (Parte 2)

CHenry [chenry@lab.matcom.uh.cu]

Definición 3:
T(n) es q( f(n) ) si es O(f(n)) y W(f(n)).

En el ejemplo anterior, el caso peor es  q(n)

Puntualmente, se puede hablar de O, q y W para el caso peor, para el caso promedio y para el mejor caso.  No siempre hay coincidencia en sus valores.

Cuando decimos que un algoritmo es O(f(n)) significa que a partir de un determinado tamaño de la entrada, el tiempo de ejecución va a ser menor o igual que f(n) multiplicado por una constante.

Para darle una cota superior al tiempo de ejecución del algoritmo, o sea, calcularle una O, se trabaja con el caso peor.

Cuando decimos que un algoritmo es W(f(n)) significa que a partir de un determinado tamaño de la entrada, el tiempo de ejecución va a ser mayor o igual que f(n) multiplicado por una constante.

NOTAS:

• Cuando el tamaño de la entrada está acotado, o sea que no tiene sentido considerar valores de n todo lo grandes que se quiera, NO tiene sentido hablar de O, W, ni  q
• En la práctica lo que hacemos es calcular O grande y a partir de ahí, afirmamos que el tiempo de ejecución del programa será de un orden proporcional a dicho valor.
• El término de cota superior no es exactamente interpretable como se hace en análisis matemático, es mejor considerar el término asíntota (cada vez más T(n) se va acercando a f(n), que es la asíntota en este caso,  pero nunca se funden ambas funciones).
• Analizar el caso de la función T(n)= an² + bn + d que es O(n²), es decir se cumple la siguiente desigualdad an² + bn + d <= cn² para n>=n0 . Destacar que a partir de un n suficientemente grande, los dos últimos términos de T(n) se vuelven despreciables pues el término en se dispara vertiginosamente, o sea, su velocidad de crecimiento. En el análisis gráfico, va siempre por encima la curva de cn² y por debajo la de T(n). Al principio existe una cierta distancia inicial que las separa, pero a medida que n va siendo suficientemente grande, esa distancia se reduce considerablemente, de forma tal que parece que ambas funciones se van a pegar. Esa distancia la establecen, precisamente los dos últimos términos de T(n), o sea, los que son despreciables cuando n es suficientemente grande.
• Una T(n) que es O(n²) también será O(n²), O(n³), .... , precisamente me quedo con la primera porque es la que más se ajusta. Debe verse que O(n²) constituye una familia de funciones, que contiene a todas aquellas funciones que son precisamente O(n²), y así sucede para todas las otras. Un miembro de la familia de O(n²), también lo será de todas las demás familias, pero a la inversa NO siempre se cumple, escojo entonces como O grande para T(n), aquella familia que menos miembros tenga, en este caso O(n²) y podemos decir que T(n) es miembro de la familia (pertenece) O(n²), aunque cuando hablamos en términos de algoritmos lo mejor es decir, “T(n) es O(n²)”
• Se debe, en cada caso, dar la cota superior e inferior que más se ajuste (exprese con mayor exactitud, o sea de las superiores, la menor posible y de las inferiores la mayor posible) al algoritmo. El caso ideal sería cuando coincidieran ambos, que es cuando entra a jugar el concepto de q.

Cálculo del Tiempo de ejecución.

El cálculo del tiempo de ejecución de un programa, sería bien engorroso, pues sería una suma de constantes c1, c2, ...., cn ( una por cada instrucción) y a su vez, el cálculo de cada una de ellas sería impracticable, pues dependería, en cada caso, de las características de la máquina donde se ejecute el programa. Por tal motivo, lo que se hace en la práctica es calcular O grande, y a partir de ahí, podemos decir, el tiempo de ejecución del programa está acotado, superiormente, por dicho valor.

Algunas reglas para calcular los ordenes O, en elementos individuales dentro del cuerpo del programa, serían las siguientes:

Regla de la SUMA:
Si tengo varios ordenes sumados, me quedo con el mayor

Regla de la PRODUCTO:
Si tengo varios ordenes multiplicados, me quedo con el producto

• Todas las operaciones atómicas son O(1). Ej: asignaciones, suma, resta, etc
• Una secuencia constante (que no dependa de n) de instrucciones es O del máximo de las O particulares correspondientes a cada instrucción de la secuencia. En este mismo sentido, si existen dos segmentos de programa p1, p2 y p2 se ejecuta inmediatamente después de ser ejecutado p1, el orden de la secuencia total, es el máximo entre el orden de p1 y el de p2, de aquí, se deduce la regla de la suma: el orden de una suma de ordenes, es el mayor orden que aparece entre los sumandos
• regla del producto: el orden de un producto de ordenes, es dicho producto.
• En un ciclo su tiempo de ejecución está acotado superiormente por la cantidad de veces que el cuerpo del mismo se ejecuta, multiplicado por el orden de la secuencia de instrucciones que se ejecuta dentro de él. Se aplica la regla del producto.
• En una sentencia del tipo if-then-else, el O de la misma se calcula mediante la suma del tiempo requerido para evaluar la condición, por lo general O(1), mas el mayor entre los O correspondientes a la secuencia de instrucciones del if y del then.

En estas reglas no se ha tenido en cuenta el caso de procesos recursivos. Por lo general la expresión de la función de tiempo para estos casos es de la forma:

a, b, y n0   son enteros positivos

La idea es que mi problema de tamaño n es descompuesto en a subproblemas de tamaño n/b, para obtener la solución del problema de tamaño n, a partir de dichos subproblemas. Consideramos que integrar las soluciones particulares de cada uno de ellos, para obtener la solución general del problema, consume un tiempo h(n)

Idea:

T(n) se subdivise en T1(n/b) ………. Ta(n/b)

Cada Ti genera una  Sol i particular para el subproblema i

h(n) es el tiempo necesario para integrar las a soluciones, Sol 1 …. Sol a, a  partir de las cuales se obtiene la solución general del problema.

Ej: Buscar el máximo en un arreglo sería:

Si el arreglo es de tamaño 1, retorno su único elemento en O(1).
De lo contrario retorno, (en O(1)) el mayor entre el máximo de su primera mitad y el de su segunda mitad.

En este ejemplo a=b= 2 y h(n) es O(1)

Algunas reflexiones interesantes ..........

Si tenemos un programa cuyo tiempo de ejecución es O(log n) (Como por ejemplo lo es el algoritmo de “búsqueda binaria o dicotómica”), podemos considerar que tenemos una versión muy eficiente, en cuanto a tiempo de ejecución, de dicho  programa.
Por ejemplo

Sabemos que es un número suficientemente grande e interpretémoslo en este caso, como el tamaño de la entrada

Si nuestro programa consume un  tiempo de ejecución de orden logarítmico, para el ejemplo en cuestión

Recordar:

sea, que procesa todo el volumen de datos de la entrada, en 20 operaciones. Lo cual da idea de lo eficiente que es dicho programa.

Si el tiempo de ejecución de un programa es O(n log n), dicho orden es casi lineal. (Como por ejemplo lo es el algoritmo de “ordenación por mezcla”), pues para valores muy grandes de n, el valor del log n, por las características de dicha función, es un número muy pequeño en comparación con el valor de n.

Ej. Un número muy grande, podría ser:

• Los tiempos de ejecución comienzan a ser respetables a partir de órdenes cuadrados. Por ejemplo: Ordenación por el método “Burbuja” que es de orden O(n²)

Cuando el tamaño de la entrada es pequeño, en algunos casos, es más conveniente usar un algoritmo de orden superior a otro.

Ej: P1 y P2 son dos programas con tiempos de ejecución T1 y T2 respectivamente que implementan la solución de un mismo problema. T1(n) = 100 n² y T2(n) = n³, T1(n) / T2(n) = 100 / n, y dicha razón es >= 1, para los n <= 100, (lo que implica que el término que aparece en el numerador es mayor que el del denominado), por tanto en tales casos, es mejor utilizar P2 para estos casos. Si las entradas se comportaran mayores que 100, entonces si es mejor usar P1 que es el de mejor orden.

Nota: En esta conferencia los estudiantes pueden manifestar dudas entre el concepto de O grande y el de o pequeña dado en análisis matemático y que también tiene una expresión para el análisis del tiempo de ejecución de un algoritmo.

Artículos relacionados:

Tiempo de ejecución (Parte 1)

Artículos relacionados