Algorit

kjoAn´lisis de Algoritmos a


´ Indice
1. Costes en tiempo y en espacio 2. Coste en los casos mejor, promedio y peor 3. Notaci´n asint´tica o o 4. Coste de los algoritmos iterativos 5. Coste de los algoritmos recursivos, teoremas maestros 1 3 4 6 6

1.

Costes en tiempo y en espacio

La caracter´ ıstica b´sica que debe tener un algoritmo es que sea correcto, a es decir, que produzca elresultado deseado en tiempo finito. Adicionalmente puede interesarnos que sea claro, que est´ bien estructurado, que sea f´cil de e a usar, que sea f´cil de implementar y que sea eficiente. a Entendemos por eficiencia de un algoritmo la cantidad de recursos de c´mputo que requiere; es decir, cu´l es su tiempo de ejecuci´n y qu´ cantidad o a o e de memoria utiliza. A la cantidad de tiempo que requierela ejecuci´n de un cierto algoritmo se o le suele llamar coste en tiempo mientras que a la cantidad de memoria que requiere se le suele llamar coste en espacio. Es evidente que conviene buscar algoritmos correctos que mantengan tan bajo como sea posible el consumo de recursos que hacen del sistema, es decir, que sean lo m´s eficientes posible. Cabe hacer notar que el concepto de eficiencia a de unalgoritmo es un concepto relativo, esto quiere decir que ante dos algoritmos correctos que resuelven el mismo problema, uno es m´s eficiente que a otro si consume menos recursos. Por tanto, podemos observar que el concepto de eficiencia y en consecuencia el concepto de coste nos permitir´ comparar a distintos algoritmos entre ellos. Si consideramos los algoritmos elementales de ordenaci´n porselecci´n y por o o inserci´n ¿c´mo podr´ o o ıamos elegir cu´l de ellos utilizar en una aplicaci´n dada? a o

1

Veremos m´s adelante que para efectos pr´cticos ambos algoritmos son similares a a y que son eficientes s´lo para ordenar secuencias con un n´mero peque˜o de o u n elementos. Sin embargo hay varias comparaciones que se pueden hacer entre ellos. Tama˜o del vector n n Num. Comparacionesn(n − 1)/2 n − 1 (min.) prop. n2 /4 (prom.) prop. n2 /2 (max.) Num. Intercambios 0 (min.) n − 1 (max.) 0 (min.) prop. n2 /4 (prom.) prop. n2 /2

Selecci´n o

Inserci´n o

n

De la tabla anterior podemos inferir que para ordenar secuencias cuyos elementos sean dif´ ıciles de comparar (las comparaciones son caras) es m´s convea niente utilizar el m´todo de ordenaci´n por inserci´n, y que estem´todo es m´s e o o e a eficiente mientras m´s ordenada est´ la secuencia de entrada. Si por el contrario a e queremos ordenar secuencias de elementos que son f´ciles de comparar (o que a tienen claves asociadas f´ciles de comparar) y en cambio los intercambios son a caros ser´ m´s conveniente utilizar el algoritmo de ordenaci´n por selecci´n. ıa a o o En general, ¿c´mo podemos elegir entre unalgoritmo y otro si ambos resuelo ven el mismo problema? Una posibilidad es hacerlo mediante pruebas emp´ ıricas. En este caso habr´ que traducir ambos algoritmos a un lenguaje de programaci´n, realiıa o zar medidas del tiempo de ejecuci´n de los programas cuando se aplican a un o conjunto de muestras de entrada y a partir de estas medidas intentar inferir el rendimiento de los programas. Pero estem´todo tiene varios inconvenientes e ya que los resultados dependen: del subconjunto de pruebas escogidas del ordenador en el que se realicen las pruebas del lenguaje de programaci´n utilizado o o del compilador, entre otros factores. Adem´s, no siempre es f´cil implementar un algoritmo (algunos pueden ser a a muy largos o complicados), por tanto, en muchas ocasiones puede ser muy util ´ poderpredecir c´mo va a comportarse un algoritmo sin tenerlo que implemeno tar. Para ello es conveniente analizar un algoritmo matem´ticamente. a Ejemplo. An´lisis de la funci´n pos min, que encuentra la posici´n del elea o o mento m´ ınimo en un vector de enteros. El coste en tiempo de un algoritmo depende del tipo de operaciones que realiza y del coste especi´ ıfico de estas operaciones. Este coste suele...