AQUI LES DEJO UNA EXPLICACION FACIL DE LO QUE COMPRENDE UN ANALISIS DE ALGORITMOS,LAS INSTANCIAS DURANTE UN ALGORITMO Y LA COMPLEJIDAD ASINTOTICA

¿Como es el Análisis de algoritmos?

Es la caracterisacion de un algoritmo refiriéndose a la cantidad de la computación y memoria que utilisara . y esto se ve de dos maneras: la dificultad del problema y la eficiencia del algoritmo en resolverlo

Calidad de un algoritmos

La calidad de un algoritmo se mide en :

-Tiempo total de computación

-Número de operaciones realizadas por el algoritmo

- Número de transiciones tomadas por la Máquina Turing que ejecuta el algoritmo

-Cantidad de memoria utilizada

- Número y tamaño de las variables

-Posición extrema a la derecha que se llega a visitar en la cinta de la Máquina Turing durante la ejecución

Cuando el algoritmo está expresado como pseudocódigo, no lo vamos a convertir en una Máquina Turing,si no que se Busca contar la cantidad de operaciones básicas que contiene el algoritmo, aquí están las opeaciones que se pueden llegar a contar:

- Aritmética simple

-Lógica simple

-Comparaciones simples

- Asignaciones simples

- Salto

Instancias

Para cada problema, hay varias instancias que son los datos particulares de entrada del problema

Dificultad de instancias

-No todas las instancias son iguales en términos de dificultad de su resolución..

- El tamaño de la entrada evidentemente afecta, pero también afecta su estructura.

-La teoría clásica de complejidad computacional se formula en términos del tamaño de la instancia

Complejidad asintótica

-Denotamos el tamaño de instancia con n

- Calculamos el número de operaciones y el consumo de memoria para varios diferentes valores de n

-Graficamos el desempeño del algoritmo en función de n

- Buscamos a una función simple que nos de una cota superior al comportamiento observado