Análisis de la complejidad de algoritmos
Páginas: 19 (4596 palabras)
Publicado: 13 de agosto de 2010
© Copyright 2003 José María Vegas Gertrudix, Madrid, España, alumno de la Facultad de Informática de la Universidad Complutense de Madrid. Todos los derechos reservados. Se puede usar y distribuir por cualquier persona la presente información sin fin lucrativo y mencionando la autoría. Este texto tiene un propósito didáctico.
CAPÍTULO 2
Análisis de la complejidad de algoritmos
1.-Introducción.
El objetivo de este tema es determinar cómo se ha de medir la complejidad de un algoritmo, de forma que sea posible compararlo con otros que resuelven el mismo problema y decidir cuál de todos ellos es más eficiente. La complejidad de un algoritmo viene dada por los recursos que consume del computador: tiempo del procesador y espacio de memoria necesarios para ejecutar el algoritmo. Unalgoritmo será tanto más eficiente cuantos menos recursos consuma. Un computador rápido no es suficiente si no se dispone de un algoritmo eficiente.
No obstante, la eficiencia suele contraponerse a la claridad del código, es decir, una mayor eficiencia suele suponer una menor comprensibilidad del código. Además, un algoritmo eficiente requiere un mayor tiempo de desarrollo. Por tanto, es mejordesarrollar rápidamente en primer lugar un algoritmo claro, aunque sea ineficiente, y optimizarlo posteriormente.
En ocasiones puede no interesarnos buscar el algoritmo más eficiente que resuelve un problema, como por ejemplo si se va a a ejecutar pocas veces o con datos de entrada de pequeño tamaño.
La complejidad de un algoritmo se cuantifica con las medidas de complejidad:
Complejidadtemporal: tiempo de ejecución del algoritmo.
Complejidad espacial: espacio de memoria que consume el algoritmo al ejecutarse.
La complejidad espacial será estudiada ocasionalmente, en situaciones especialmente relevantes, por lo que no trataremos más sobre ella. En general, interesa sobre todo conseguir buenas complejidades temporales, lo que con frecuencia conlleva obtener peores complejidadesespaciales.
La complejidad temporal de un algoritmo depende de:
El tamaño de los datos de entrada.
El valor o contenido de los datos de entrada.
El código generado por el compilador, es decir, la eficiencia del compilador.
El computador concreto utilizado para ejecutar el algoritmo.
Vamos a realizar un estudio teórico de la complejidad de los algoritmos y, por tanto, prescindiremos delos aspectos empíricos o prácticos.
El tamaño de los datos de entrada se determina en función del tipo de datos de dichos datos de entrada. Por ejemplo, si el dato de entrada es un vector o un fichero, el tamaño será generalmente la longitud del vector o la del fichero; si es una matriz cuadrada, su dimensión; si es un número, su valor o su número de dígitos; etc. En otros casos más complicados,se indicará apropiadamente cómo determinar el tamaño de los datos de entrada.
Una vez que hemos determinado el tamaño de los datos de entrada, analizaremos la eficiencia de aquellos ejemplares de dicho tamaño en los que el algoritmo emplea más tiempo para ejecutarse. De este modo, se obtiene una cota superior del tiempo de ejecución para cualquier ejemplar. Se dice entonces que vamos arealizar un análisis de la eficiencia en el caso peor. La complejidad en el caso peor proporciona una medida pesimista pero fiable.
El tiempo absoluto que tarda un algoritmo A en procesar una entrada concreta x lo notaremos como tA(x).
El tiempo de ejecución del algoritmo A en el caso peor, que denotaremos por TA(n), se define por la función TA(n) = max {tA(x) / x es de tamaño n}.
Sin embargo,en nuestro análisis de la eficiencia del algoritmo en el caso peor, no consideraremos la potencia del computador concreto utilizado para ejecutar el algoritmo ni la eficiencia del compilador que determina la mayor o menor optimización del código generado por éste. Éste es el denominado criterio asintótico, que quiere decir que no pretendemos obtener la forma exacta de la función de complejidad...
CAPÍTULO 2
Análisis de la complejidad de algoritmos
1.-Introducción.
El objetivo de este tema es determinar cómo se ha de medir la complejidad de un algoritmo, de forma que sea posible compararlo con otros que resuelven el mismo problema y decidir cuál de todos ellos es más eficiente. La complejidad de un algoritmo viene dada por los recursos que consume del computador: tiempo del procesador y espacio de memoria necesarios para ejecutar el algoritmo. Unalgoritmo será tanto más eficiente cuantos menos recursos consuma. Un computador rápido no es suficiente si no se dispone de un algoritmo eficiente.
No obstante, la eficiencia suele contraponerse a la claridad del código, es decir, una mayor eficiencia suele suponer una menor comprensibilidad del código. Además, un algoritmo eficiente requiere un mayor tiempo de desarrollo. Por tanto, es mejordesarrollar rápidamente en primer lugar un algoritmo claro, aunque sea ineficiente, y optimizarlo posteriormente.
En ocasiones puede no interesarnos buscar el algoritmo más eficiente que resuelve un problema, como por ejemplo si se va a a ejecutar pocas veces o con datos de entrada de pequeño tamaño.
La complejidad de un algoritmo se cuantifica con las medidas de complejidad:
Complejidadtemporal: tiempo de ejecución del algoritmo.
Complejidad espacial: espacio de memoria que consume el algoritmo al ejecutarse.
La complejidad espacial será estudiada ocasionalmente, en situaciones especialmente relevantes, por lo que no trataremos más sobre ella. En general, interesa sobre todo conseguir buenas complejidades temporales, lo que con frecuencia conlleva obtener peores complejidadesespaciales.
La complejidad temporal de un algoritmo depende de:
El tamaño de los datos de entrada.
El valor o contenido de los datos de entrada.
El código generado por el compilador, es decir, la eficiencia del compilador.
El computador concreto utilizado para ejecutar el algoritmo.
Vamos a realizar un estudio teórico de la complejidad de los algoritmos y, por tanto, prescindiremos delos aspectos empíricos o prácticos.
El tamaño de los datos de entrada se determina en función del tipo de datos de dichos datos de entrada. Por ejemplo, si el dato de entrada es un vector o un fichero, el tamaño será generalmente la longitud del vector o la del fichero; si es una matriz cuadrada, su dimensión; si es un número, su valor o su número de dígitos; etc. En otros casos más complicados,se indicará apropiadamente cómo determinar el tamaño de los datos de entrada.
Una vez que hemos determinado el tamaño de los datos de entrada, analizaremos la eficiencia de aquellos ejemplares de dicho tamaño en los que el algoritmo emplea más tiempo para ejecutarse. De este modo, se obtiene una cota superior del tiempo de ejecución para cualquier ejemplar. Se dice entonces que vamos arealizar un análisis de la eficiencia en el caso peor. La complejidad en el caso peor proporciona una medida pesimista pero fiable.
El tiempo absoluto que tarda un algoritmo A en procesar una entrada concreta x lo notaremos como tA(x).
El tiempo de ejecución del algoritmo A en el caso peor, que denotaremos por TA(n), se define por la función TA(n) = max {tA(x) / x es de tamaño n}.
Sin embargo,en nuestro análisis de la eficiencia del algoritmo en el caso peor, no consideraremos la potencia del computador concreto utilizado para ejecutar el algoritmo ni la eficiencia del compilador que determina la mayor o menor optimización del código generado por éste. Éste es el denominado criterio asintótico, que quiere decir que no pretendemos obtener la forma exacta de la función de complejidad...
Leer documento completo
Regístrate para leer el documento completo.