View
213
Download
1
Category
Preview:
Citation preview
Complejidad de los algoritmos
Walter Henríquez Esparza
Estudiante Ingeniería Informática
Docente: Pilar Pardo H.
La Complejidad se
mide en cuanto a la cantidad de Tiempo y
Espacio que un Algoritmo necesita para realizar sus
operaciones.
Su Medición:
En Espacio se basa en la Memoria Utilizada para su ejecución y las Estructuras de Datos usadas para su implementación
En Tiempo se basa en las Operaciones del Algoritmo y el Tamaño de sus entradas.
La Complejidad y sus Casos:
Peor Caso:Número Mayor de Operaciones realizadas por un Algoritmo para dar Solución al problema.
Caso Promedio:Número
Promedio de Operaciones realizadas por un Algoritmo para dar Solución al problema.
Tiempo de Ejecución
Para medir esta Complejidad se define:
T(n)A través de su Ejecución, se calcula el
número de
instrucciones ejecutadas,
multiplicadas por
el tiempo que utiliza cada instrucción, a raíz de la cantidad y tamaño de las entradas realizadas.
La Potencia de un Algoritmo es necesariaanalizarla sin tomar en cuenta la máquina que loejecuta y de la capacidad del que lo crea.
Así como cuando un Algoritmo es creado para resolver un problema de
gran altura o complejidad.
Todo apunta a que el comportamiento de los Algoritmos es Proporcional al
tamaño del problema para el cual fue generado, si es Definido queda que: Ntiende a INFINITO Y su Comportamiento seríaAsintótico.
Es definida a través de números naturales N que se estiman con
el tiempo
o espacio del Algoritmo y en la longitud de la entrada.
Función Asintótica se le llama al comportamiento que estas tienen a raíz de su
Tasa de Crecimiento.Nunca son Negativas
La Complejidad del Algoritmo tiene como notación Big - O
Lo que se busca es poder juntar dichas funciones en Familias, que tengan el mismo comportamiento asintótico, y serán definidas como:
«Orden de Complejidad»
Complejidad Terminología
O(1) Complejidad constanteO(log n) Complejidad logarítmicaO(n) Complejidad linealO(n log n) Complejidad n log nO(n^b) Complejidad polinómicaO(b^n) Complejidad exponencialO(n!) Complejidad factorial
Recommended