Como medir la complejidad
Páginas: 8 (1785 palabras)
Publicado: 24 de agosto de 2013
EFICIENCIA DE ALGORITMOS
A la hora de estudiar la eficiencia de distintos algoritmos es necesario distinguir problemas de ejemplares.
Un problema sería una “proposición dirigida a averiguar el modo de obtener un resultado cuando ciertos datos son conocidos.
Un ejemplar, en cambio, es un “individuo de una especie o género
Un ejemplo de Problema seria multiplicar dos números enteros oresolver una ecuación de 2do grado; mientras que los ejemplares de dichos problemas serian 4*5 o xˆ2+x-1.
Un problema dado puede tener un número infinito de ejemplares y un algoritmo que afirme resolver un problema debe resolver todos los ejemplares del mismo. Si hay un ejemplar que no pueda ser resuelto el algoritmo es incorrecto.
No todos los ejemplares de un problema son iguales, al noser iguales la eficiencia del algoritmo puede variar en función del ejemplar o del grupo de ejemplares. Cuando analizamos un algoritmo es necesario saber que pueden darse tres tipos de casos:
1 CASO MEJOR
Se trata de aquellos ejemplares del problema en los que el algoritmo es más eficiente. Cuando son necesarios el mínimo número de cálculos.; por ejemplo: multiplicar un número por cero,insertar en una lista vacía, ordenar un vector que ya está ordenado, entre otros.
2 CASO PEOR
Se trata de aquellos ejemplares del problema en los que el algoritmo es menos eficiente (no siempre existe el caso peor). Cuando son necesarios el máximo número de cálculos. Ejemplos: insertar al final de una lista, ordenar un vector que está ordenado en orden inverso, entre otros.
3 CASO PROMEDIOSe trata del resto de ejemplares del problema. Por ejemplo: multiplicar dos números enteros distintos de cero, ordenar un vector que no está ordenado ni en orden directo ni inverso, entre otros.
Es el caso que más nos debería preocupar puesto que será el más habitual, sin embargo no siempre se puede calcular (habría que saber cuáles son las probabilidades de los distintos ejemplares.MIDIENDO LA EFICIENCIA
Tenemos que nos interesa saber qué algoritmo utiliza más eficientemente los recursos, en general, el tiempo de ejecución.
La eficiencia además de depender del tamaño de los ejemplares depende de la naturaleza de los mismos: caso mejor, caso peor y caso promedio.
Para calcular la eficiencia es posible considerar sólo el número de veces que se debe ejecutar una operaciónelemental pues éstas tendrán un coste unitario.
¿En qué “unidad” mediremos esta eficiencia?
La solución está en el principio de invarianza, dicho principio afirma que dos implementaciones distintas del mismo algoritmo no diferirán en su eficiencia más que en una constante multiplicativa.
De esta forma, no habrá unidad para medir la eficiencia, nos limitaremos a decir que el tiempo de ejecuciónde un algoritmo será t(n), es decir, una función del tamaño de los ejemplares; en unas máquinas el tiempo de ejecución será a·t(n) y en otras será b·t(n).
Sabemos que podemos medir la eficiencia de un algoritmo como una función t(n).Al momento de analizar un algoritmo principalmente nos interesa la forma en la cual el algoritmo se comporta al aumentar el tamaño de los datos, esto se conoce comoeficiencia asintótica de un algoritmo y nos permitirá comparar distintos algoritmos.
Notación:
La notación anterior básicamente nos dice que si tenemos un algoritmo cuyo tiempo de ejecución es f(n) podemos encontrar otra función de n, g(n), y un tamaño de problema de tal forma que g(n) acota superiormente al tiempo de ejecución para todos los problemas de tamaño superior a
Estanotación, como veremos a continuación, facilitará en las comparaciones de eficiencia entre algoritmos diferentes.
El orden de complejidad se define como una función que domina la ecuación que expresa en forma exacta el tiempo de ejecución del algoritmo.
Una operación elemental es aquella cuyo tiempo de ejecución tiene una cota superior constante que sólo depende de su implementación. Se...
A la hora de estudiar la eficiencia de distintos algoritmos es necesario distinguir problemas de ejemplares.
Un problema sería una “proposición dirigida a averiguar el modo de obtener un resultado cuando ciertos datos son conocidos.
Un ejemplar, en cambio, es un “individuo de una especie o género
Un ejemplo de Problema seria multiplicar dos números enteros oresolver una ecuación de 2do grado; mientras que los ejemplares de dichos problemas serian 4*5 o xˆ2+x-1.
Un problema dado puede tener un número infinito de ejemplares y un algoritmo que afirme resolver un problema debe resolver todos los ejemplares del mismo. Si hay un ejemplar que no pueda ser resuelto el algoritmo es incorrecto.
No todos los ejemplares de un problema son iguales, al noser iguales la eficiencia del algoritmo puede variar en función del ejemplar o del grupo de ejemplares. Cuando analizamos un algoritmo es necesario saber que pueden darse tres tipos de casos:
1 CASO MEJOR
Se trata de aquellos ejemplares del problema en los que el algoritmo es más eficiente. Cuando son necesarios el mínimo número de cálculos.; por ejemplo: multiplicar un número por cero,insertar en una lista vacía, ordenar un vector que ya está ordenado, entre otros.
2 CASO PEOR
Se trata de aquellos ejemplares del problema en los que el algoritmo es menos eficiente (no siempre existe el caso peor). Cuando son necesarios el máximo número de cálculos. Ejemplos: insertar al final de una lista, ordenar un vector que está ordenado en orden inverso, entre otros.
3 CASO PROMEDIOSe trata del resto de ejemplares del problema. Por ejemplo: multiplicar dos números enteros distintos de cero, ordenar un vector que no está ordenado ni en orden directo ni inverso, entre otros.
Es el caso que más nos debería preocupar puesto que será el más habitual, sin embargo no siempre se puede calcular (habría que saber cuáles son las probabilidades de los distintos ejemplares.MIDIENDO LA EFICIENCIA
Tenemos que nos interesa saber qué algoritmo utiliza más eficientemente los recursos, en general, el tiempo de ejecución.
La eficiencia además de depender del tamaño de los ejemplares depende de la naturaleza de los mismos: caso mejor, caso peor y caso promedio.
Para calcular la eficiencia es posible considerar sólo el número de veces que se debe ejecutar una operaciónelemental pues éstas tendrán un coste unitario.
¿En qué “unidad” mediremos esta eficiencia?
La solución está en el principio de invarianza, dicho principio afirma que dos implementaciones distintas del mismo algoritmo no diferirán en su eficiencia más que en una constante multiplicativa.
De esta forma, no habrá unidad para medir la eficiencia, nos limitaremos a decir que el tiempo de ejecuciónde un algoritmo será t(n), es decir, una función del tamaño de los ejemplares; en unas máquinas el tiempo de ejecución será a·t(n) y en otras será b·t(n).
Sabemos que podemos medir la eficiencia de un algoritmo como una función t(n).Al momento de analizar un algoritmo principalmente nos interesa la forma en la cual el algoritmo se comporta al aumentar el tamaño de los datos, esto se conoce comoeficiencia asintótica de un algoritmo y nos permitirá comparar distintos algoritmos.
Notación:
La notación anterior básicamente nos dice que si tenemos un algoritmo cuyo tiempo de ejecución es f(n) podemos encontrar otra función de n, g(n), y un tamaño de problema de tal forma que g(n) acota superiormente al tiempo de ejecución para todos los problemas de tamaño superior a
Estanotación, como veremos a continuación, facilitará en las comparaciones de eficiencia entre algoritmos diferentes.
El orden de complejidad se define como una función que domina la ecuación que expresa en forma exacta el tiempo de ejecución del algoritmo.
Una operación elemental es aquella cuyo tiempo de ejecución tiene una cota superior constante que sólo depende de su implementación. Se...
Leer documento completo
Regístrate para leer el documento completo.