algoritmos

Páginas: 11 (2737 palabras) Publicado: 2 de diciembre de 2013
11. ¿Cómo medir la eficiencia de un algoritmo?
11.1 La función de trabajo, un primer acercamiento a la eficiencia de un algoritmo
La pregunta de este capítulo es relativamente sencilla, pero de un campo de aplicación muy
amplio: ¿qué sucede con los algoritmos cuándo crece el número de datos con los cuales trabaja?
Debemos anticipar que la respuesta no es obvia. ¡Bienvenidos al universo de lacomplejidad
computacional!
La función de trabajo es la forma más común de acercarse al problema de la eficiencia de los
algoritmos. En este capítulo abordaremos los enfoques para llevar a cabo dicha medición, sus
implicaciones prácticas y algunas recomendaciones didácticas necesarias para abordarla en la
labor docente.
El primer paso para ello es dejar establecido el concepto de eficiencia:“Eficiencia es la capacidad de un sistema software para exigir la menor cantidad
posible de recursos hardware, tales como tiempo del procesador, espacio ocupado
de memoria interna y externa o ancho de banda utilizado en los dispositivos de
1
comunicación.”
Para aislar esta característica de otras cualidades del software, conviene medir el consumo de
recursos entre dos sistemas cuando estosrealizan la misma labor.
A manera de ejemplo, compare estos dos códigos que cubren exactamente la misma tarea.
long int sumatoria (int a) {
long int suma = 0;
int i;
if (a == 0)
return 0;
else {
for (i = a; i > 0; i--)
suma += i;
return(suma);
}
}

long int sumatoria (int dato) {
return(dato*(dato+1)/2);
}
De hecho, constituyen rutinas intercambiables y equivalentes; cualquiera deellas puede
combinar con el mismo programa principal.

1

Meyer, Bertrand. Construcción de software Orientado a Objetos. Prentice-Hall. Segunda edición. Madrid,
1999. pág. 8.
.

Reflexión 11-1. Manejemos claramente el concepto de eficiencia
La eficiencia suele confundirse con otras características de software. Por
ejemplo: si un software falla se suele decir que no es eficiente,cuando en realidad
el software no es correcto. O si no es fácil de manejar se dice igualmente que no
eficiente, cuando en realidad lo que no tiene es facilidad de uso.
Seamos exigentes en cuanto a la delimitación del concepto, pues de otra
manera es muy difícil de cuantificar.

long int sumatoria (int a);
main() {
int j;
long int sumaux;
printf("Este programa genera una tabla desumatorias.\n\n");
printf("
NUMERO
SUMATORIA\n");
for (j=0; j ∝

2

por eso se dice, de manera un tanto simplificada, que el orden de la función es n , es decir,
que el orden del algoritmo es de naturaleza cuadrática.
Con pocos datos, el resultado no es significativo. Sin embargo, ¿qué pasaría si se deseara
generar la tabla hasta 1000?

f(n) = 1000 * 10001 / 2
= 500500
¿Y para medio millón deregistros?
f(n) = 500000 * 500001 / 2
= 125,000,250,000
No se extrañe si la medición física para el caso 1 ronda ya los 15 minutos.
Pareciera exagerado probar con 500000 registros. Sólo dos ejemplos: el número de registros en
el histórico anual de una nómina de una empresa de unos 500 empleados ronda, justamente, el
medio millón de registros; algún banco de tamaño medio y cobertura nacionalrealiza, en un día de
baja actividad, un millón de transacciones. La función de trabajo en esos casos es parte de la vida
cotidiana.
A estos niveles ganamos poco tratando de cambiar el hardware. Por lo común, la eficiencia se
mejora más por el algoritmo empleado. Es relativamente sencillo demostrar que el código
simplificado de la sumatoria
long int sumatoria (int dato) {return(dato*(dato+1)/2);
}
es de naturaleza lineal, pues hay una sola instrucción para devolver la sumatoria del número
indicado. Así, para sacar la tabla de los primeros 15 números se tendrán que aplicar 15
instrucciones. Generalizando:
f(n) = n , donde n es el límite de la tabla comenzando en 1.
Una mejora enorme con respecto al código de la primera subrutina analizada.

Ejercicios sugeridos
Los...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Algoritmo
  • Algoritmo
  • Algoritmos
  • Algoritmos
  • Algoritmos
  • Algoritmos
  • Algoritmos
  • Algoritmos

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS