Estructura de datos

ESTRUCTURA DE DATOS Unidad 1 Análisis de Algoritmos.

1 Análisis de algoritmos.
1.1 Concepto Complejidad Algoritmos.
La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo seconsidera farragoso. Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es unconcepto difícil de entender. Entender la complejidad es importante porque a la hora de resolver muchos problemas, utilizamos algoritmos ya diseñados. Saber valorar su valor de complejidad puede ayudarnos mucho a conocer cómo se va a comportar el algoritmo e incluso a escoger uno u otro. Primeramente, debemos tener claro qué es un algoritmo. Podemos entender por algoritmo una secuencia deinstrucciones cuyo objetivo es la resolución de un problema. El término clave aquí es el de problema.

1.2 Aritmética Notación O.
En general, el tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puedeconsiderar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2) Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2), siendo N el número de vérticeséste. La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos de entrada delalgoritmo.

Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución, es decir, el peor caso. A veces ocurre que no hay que prestar demasiada atención a esto. Conviene diferenciar entre el peor caso y el esperado. Por ejemplo, el tiempo de ejecución del algoritmo Quick Sort es de O(N2). Sin embargo, en la práctica este caso no se da casinunca y la mayoría de los casos son proporcionales a N•logN. Es por ello que se utiliza esta última expresión para este método de ordenación. Una definición rigurosa de esta notación es la siguiente: Una función g(N) pertenece a O(f(N)) si y sólo si existen las constantes c0 y N0 tales que: |g(N)| ‹= |c0•f(N)| , para todo N ›= N0. Clasificación de problemas Los problemas matemáticos se puedendividir en primera instancia en dos grupos: Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo. Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo. Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solución, pues muchos problemas que disponen de algoritmos para su resolución son inabordables para un computadorpor el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos: intratables: aquellos para los que no es factible obtener su solución. tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable. Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemaspara los que se conoce un algoritmo polinomio que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejores algoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.

1.3...