Introduccion al analisis de algoritmos
Páginas: 21 (5065 palabras)
Publicado: 7 de marzo de 2010
Tema 14
Introducci´n al an´lisis de algoritmos o a
Sin embargo, cuando ya llevaban corriendo una media hora o as´ y estaban completamente ı, secos otra vez, el Dodo dijo de repente en voz alta: ((¡La carrera ha terminado!)), y se agruparon todos a su alrededor, jadeando y preguntado: ((Pero, ¿qui´n ha ganado?)). e El Dodo no pod´ contestar a esta pregunta sin meditarlo mucho antes, ypermaneci´ largo ıa o rato con un dedo apretado en la frente (en la postura que normalmente veis a Shakespeare en los retratos), mientras el resto esperaba en silencio. LEWIS CARROLL, Alicia en el Pa´ de las Maravillas. ıs Si tuvieses que escoger un programa entre varios que resuelven un mismo problema, ¿en funci´n de o qu´ escoger´ e ıas?: ¿de su elegancia?, ¿de la legibilidad?, ¿del interfaz deusuario?, ¿de su velocidad de ejecuci´n?, ¿de la memoria que consume? No cabe duda de que todos los factores influyen. Nosotros o consideraremos aqu´ criterios basados en la eficiencia, es decir, en el mejor aprovechamiento de los ı recursos computacionales. Nuestro objeto de estudio ser´n los m´todos de resoluci´n de problemas, a e o es decir, los algoritmos, y no los programas, o sea, sus implementacionesconcretas usando diferentes lenguajes de programaci´n. o Estudiaremos dos factores: El coste o complejidad espacial, es decir, la cantidad de memoria que consume. El coste o complejidad temporal, o sea, el tiempo que necesita para resolver un problema. Ambos determinan el coste o complejidad computacional. No siempre coincidir´n consumo espacial a o ´ptimo con m´ ınimo coste temporal; es m´s,ambos factores entrar´n, normalmente, en competencia. a a En ocasiones estaremos obligados, pues, a adoptar compromisos razonables entre ambos costes. Centraremos el estudio, principalmente, en el an´lisis de la complejidad temporal de los algorita mos. Empezaremos proponiendo una aproximaci´n emp´ o ırica consistente en implementar diferentes programas que resuelven un mismo problema (con el mismo odiferentes algoritmos) y medir y comparar los tiempos de ejecuci´n. Veremos que, en principio, resulta m´s determinante una correcta o a elecci´n del algoritmo que los detalles de implementaci´n o, incluso, que la elecci´n de un lenguaje o o o de programaci´n frente a otro. La aproximaci´n emp´ o o ırica supone un notable esfuerzo en tanto que obliga a implementar diferentes programas,prepararlos para hacer factible la medida de tiempos y realizar diferentes experimentos que nos permitan extraer conclusiones. Presentaremos una aproximaci´n m´s te´rica que permitir´ arrojar luz sobre la eficiencia de los algoritmos sin necesidad de o a o a implementarlos y realizar experimentos.
14.1.
Complejidad temporal: una aproximaci´n emp´ o ırica
La aproximaci´n emp´ o ırica se basa en larealizaci´n de estudios comparativos basados en la realizaci´n o o de experimentos de medici´n de tiempos de ejecuci´n. Ilustraremos el problema de la medici´n de o o o
Volumen II: C
345
14.1 Complejidad temporal: una aproximaci´n emp´ o ırica
versi´n 1.02 o
tiempos con un ejemplo concreto. Mediremos tiempo de ejecuci´n con varios programas que resuelven o un mismo problema: laordenaci´n de un vector de enteros. Naturalmente, el tiempo de ejecuci´n o o depender´ del tama˜o del vector a ordenar, as´ que nuestro estudio considerar´ la dependencia del a n ı a tiempo en funci´n de dicho tama˜o. o n Empecemos presentando un programa Python que resuelve el problema mediante el m´todo de e la burbuja:
ordena_burbuja.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2425
from random import randrange def rellena (talla, rango): valores = [0] * talla for i in range(talla): valores[i] = randrange(0, rango) return valores def burbuja (valores): nuevo = valores[:] for i in range(len(nuevo)): for j in range(len(nuevo)-1-i): if nuevo[j] > nuevo[j+1]: nuevo[j], nuevo[j+1] = nuevo[j+1], nuevo[j] return nuevo # Programa principal talla = 1000 rango = 100000 vector =...
Introducci´n al an´lisis de algoritmos o a
Sin embargo, cuando ya llevaban corriendo una media hora o as´ y estaban completamente ı, secos otra vez, el Dodo dijo de repente en voz alta: ((¡La carrera ha terminado!)), y se agruparon todos a su alrededor, jadeando y preguntado: ((Pero, ¿qui´n ha ganado?)). e El Dodo no pod´ contestar a esta pregunta sin meditarlo mucho antes, ypermaneci´ largo ıa o rato con un dedo apretado en la frente (en la postura que normalmente veis a Shakespeare en los retratos), mientras el resto esperaba en silencio. LEWIS CARROLL, Alicia en el Pa´ de las Maravillas. ıs Si tuvieses que escoger un programa entre varios que resuelven un mismo problema, ¿en funci´n de o qu´ escoger´ e ıas?: ¿de su elegancia?, ¿de la legibilidad?, ¿del interfaz deusuario?, ¿de su velocidad de ejecuci´n?, ¿de la memoria que consume? No cabe duda de que todos los factores influyen. Nosotros o consideraremos aqu´ criterios basados en la eficiencia, es decir, en el mejor aprovechamiento de los ı recursos computacionales. Nuestro objeto de estudio ser´n los m´todos de resoluci´n de problemas, a e o es decir, los algoritmos, y no los programas, o sea, sus implementacionesconcretas usando diferentes lenguajes de programaci´n. o Estudiaremos dos factores: El coste o complejidad espacial, es decir, la cantidad de memoria que consume. El coste o complejidad temporal, o sea, el tiempo que necesita para resolver un problema. Ambos determinan el coste o complejidad computacional. No siempre coincidir´n consumo espacial a o ´ptimo con m´ ınimo coste temporal; es m´s,ambos factores entrar´n, normalmente, en competencia. a a En ocasiones estaremos obligados, pues, a adoptar compromisos razonables entre ambos costes. Centraremos el estudio, principalmente, en el an´lisis de la complejidad temporal de los algorita mos. Empezaremos proponiendo una aproximaci´n emp´ o ırica consistente en implementar diferentes programas que resuelven un mismo problema (con el mismo odiferentes algoritmos) y medir y comparar los tiempos de ejecuci´n. Veremos que, en principio, resulta m´s determinante una correcta o a elecci´n del algoritmo que los detalles de implementaci´n o, incluso, que la elecci´n de un lenguaje o o o de programaci´n frente a otro. La aproximaci´n emp´ o o ırica supone un notable esfuerzo en tanto que obliga a implementar diferentes programas,prepararlos para hacer factible la medida de tiempos y realizar diferentes experimentos que nos permitan extraer conclusiones. Presentaremos una aproximaci´n m´s te´rica que permitir´ arrojar luz sobre la eficiencia de los algoritmos sin necesidad de o a o a implementarlos y realizar experimentos.
14.1.
Complejidad temporal: una aproximaci´n emp´ o ırica
La aproximaci´n emp´ o ırica se basa en larealizaci´n de estudios comparativos basados en la realizaci´n o o de experimentos de medici´n de tiempos de ejecuci´n. Ilustraremos el problema de la medici´n de o o o
Volumen II: C
345
14.1 Complejidad temporal: una aproximaci´n emp´ o ırica
versi´n 1.02 o
tiempos con un ejemplo concreto. Mediremos tiempo de ejecuci´n con varios programas que resuelven o un mismo problema: laordenaci´n de un vector de enteros. Naturalmente, el tiempo de ejecuci´n o o depender´ del tama˜o del vector a ordenar, as´ que nuestro estudio considerar´ la dependencia del a n ı a tiempo en funci´n de dicho tama˜o. o n Empecemos presentando un programa Python que resuelve el problema mediante el m´todo de e la burbuja:
ordena_burbuja.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2425
from random import randrange def rellena (talla, rango): valores = [0] * talla for i in range(talla): valores[i] = randrange(0, rango) return valores def burbuja (valores): nuevo = valores[:] for i in range(len(nuevo)): for j in range(len(nuevo)-1-i): if nuevo[j] > nuevo[j+1]: nuevo[j], nuevo[j+1] = nuevo[j+1], nuevo[j] return nuevo # Programa principal talla = 1000 rango = 100000 vector =...
Leer documento completo
Regístrate para leer el documento completo.