Complejidad de algoritmos

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación

Universidad Nororiental Privada “Gran Mariscal de Ayacucho”

Asignatura: Analisis y diseño de algoritmos

Complejidad de algoritmos

Docente:                                                                                                      Bachiller:

    Zambrano Erika                                                             Dilan Peña C.I: 29.643.506

Marzo de 2023

Clases de complejidad

En la teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas computacionales de complejidad relacionada basada en recursos. Los dos recursos más comúnmente analizados son el tiempo y la memoria.

Existen varias clases de complejidad, pero algunas de las más comunes son las siguientes:

Clase P: Esta es la clase de problemas que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial. Es decir, si el tamaño del problema es n, entonces el tiempo de ejecución del algoritmo para resolverlo será de O(n^k), donde k es una constante. Los problemas en esta clase se consideran fácilmente solucionables.

Clase NP: Esta es la clase de problemas que pueden ser verificados en tiempo polinomial por una máquina de Turing no determinista. Es decir, si se presenta una solución a un problema, esta puede ser verificada en tiempo polinomial. Sin embargo, no se sabe si estos problemas pueden ser resueltos en tiempo polinomial. Los problemas en esta clase se consideran difíciles de resolver, pero una solución puede ser verificada rápidamente.

Clase NP-Completo: Esta es una clase de problemas en la que todos los problemas en NP pueden ser reducidos en tiempo polinomial a un problema en esta clase. Esto significa que si se encuentra un algoritmo de tiempo polinomial para resolver cualquier problema NP-Completo, se podría usar para resolver cualquier problema en NP en tiempo polinomial. Los problemas en esta clase son considerados muy difíciles de resolver.

Clase NP-Difícil: Esta es la clase de problemas que son al menos tan difíciles como los problemas en NP-Completo, pero no necesariamente están en NP. Es decir, si un problema NP-Difícil pudiera ser resuelto en tiempo polinomial, entonces todos los problemas en NP podrían ser resueltos en tiempo polinomial.

Clase PSPACE: Esta es la clase de problemas que pueden ser resueltos por una máquina de Turing con un espacio de memoria polinomial. Esta clase incluye todos los problemas en P y NP, así como otros problemas que requieren más memoria.

Estas clases de complejidad son útiles para entender la complejidad de los problemas computacionales y para diseñar algoritmos que puedan resolverlos de manera eficiente. Además, la clasificación de los problemas en estas clases también tiene implicaciones importantes para la criptografía y la teoría de la computación.

Medición empírica de rendimiento

La medición empírica de rendimiento se refiere al proceso de recopilar y analizar datos reales sobre el rendimiento de un sistema o proceso en lugar de depender únicamente en teorías o suposiciones. En términos generales, implica la recolección de datos mediante la observación directa y el análisis estadístico de los mismos para obtener una comprensión objetiva del rendimiento de un sistema o proceso.

En el ámbito empresarial, la medición empírica de rendimiento puede ser una herramienta valiosa para mejorar la eficiencia y la eficacia de los procesos, identificar problemas y oportunidades de mejora, y tomar decisiones informadas en base a datos reales.

...