martes, 31 de mayo de 2011

COMPLEJIDAD DE UN ALGORITMO

Complejidad de Algoritmos
La eficiencia es uno de los tres principales atributos deseables que debe poseer un algoritmo. [¿Cuáles son los otros dos?] También es algo que tenemos que ser capaces de medir o estimar si vamos a discutir esto con los que se examinará o utilice nuestro algoritmos. Determinación de la eficiencia implica el conteo y análisis. Nuestro enfoque aquí se cuenta - determinar exactamente cómo son algoritmos rápidos.
Comencemos por examinar los dos fragmentos del programa en la figura 1.
Figura 1 - Programas de recuento
¿Cuál es el valor de x al final de cada uno de ellos? En la figura 1a, incrementamos x veces por una n en el bucle de repetición y luego hacerlo de nuevo en el segundo bucle. Esto establece x n + n o 2n.
El código en la figura 1b, en cambio, contiene un bucle anidado. En este fragmento del programa, x se incrementa n veces en el bucle interior como antes. En otras palabras, el lazo interno añade n con el valor de x. Al mismo tiempo, el bucle fuera de las fuerzas del bucle interior para ser ejecutado n veces. Esto significa que Add N to X exactamente n veces. Así, nos encontramos con un valor de n * n o 2 para x.
[Este pequeño ejemplo nos dice algo acerca de la complejidad y la estructura del programa. Parece que la adición se lleva a cabo con bucles anidada y la multiplicación se puede hacer con la profundidad de anidamiento dos. ¿Qué puede hacerse con tres bucles anidados?]
Este ejemplo también ilustra una regla importante de tareas relativas a la dependencia de los cuales ciclo de anidación es un buen ejemplo.
Si las tareas se llevan a cabo de forma independiente, que sume los resultados juntos. Pero, si las tareas están entrelazadas (por ejemplo, en los bucles que dependen unos de otros), los resultados se multiplican.

No hay comentarios:

Publicar un comentario