Falta foto :c

Complejidad de los Algoritmos

Claudio Marín

Qué es la complejidad de un

algoritmo

Para definir la complejidad de un algoritmo es necesario conocer el tamaño del problema a resolver

entre mas grande el problema mas grande el algoritmo.

La complejidad se mide en dos recursos que un algoritmo necesita: Tiempo y Espacio.

La complejidad se define por el tiempo que demora un algoritmo para la ejecución de sus operaciones.

Recurso Tiempo

Recurso Espacio

La complejidad se define por la cantidad de memoria requerida para su ejecución.

Cada algoritmo se comporta de forma diferente dependiendo de las variables de entradas asignadas.

Es necesario estudiar su comportamiento considerando su peor caso y mejor caso.

Indica cuantas operaciones tiene que realizar un algoritmo para garantizar que va a llegar a una solucion.

Peor Caso

Se busca el promedio de operaciones realizadas para la solución de un problema considerando todas las posibles

entrada.

Caso Promedio

Indica que realiza rápidamente su ejecución.

Mejor Caso

El análisis de algoritmo busca como crece el tiempo de ejecuciónEl análisis de algoritmo busca como

crece el tiempo de ejecución

El análisis de algoritmo busca como crece el tiempo de ejecución

El tiempo de ejecución se denomina: T(n)

Se puede medir: Ejecutando el programa.Calculando sobre el código. Multiplicando por el tiempo de cada instrucción.

Notación Asintótica

La potencia de los algoritmos se analiza independientemente de la potencia de la maquina, el

código y capacidad del programador

Matemáticamente, cuando N tienda a infinito siempre que algo tiende a infinito

se habla de un comportamiento asintótico.

Dependiendo del tamaño del problema se determinara como se analizara el comportamiento de un algoritmo.

se denomina asintótica ya que se analiza el comportamiento de las funciones en base a su tasa de crecimiento

Su dominio son los números naturales (N).Estimada por el tiempo de ejecución o espacio de memoria.Se denota como BIG-O.No son negativas.

Se identifican familias de funciones usando como criterio su comportamiento asintótico

A las funciones con el mismo comportamiento se les denomina un

"orden de complejidad (O)"