Analisis de algoritomo (complejidad)
-
Upload
marco-nanjari -
Category
Documents
-
view
115 -
download
0
Transcript of Analisis de algoritomo (complejidad)
Es el tiempo de ejecuciónde cualquier programa en base a
'n' datos de entrada.
Según el tamaño del problema ya que el tiempo de ejecución está dado por
los n datos de entrada
Los datos se estructuran
de forma
Interna: dentro de un sistema y tiene
2 estructuras
Estáticas (vectores y matrices)
Dinámica se clasifica en:
Externa: archivos de otra compañía
Lineales (Pilas, Listas,
Colas)
No Lineales (Arboles, Gráficos)
Base de datos
Archivos
El peor caso consiste en verificar cuántas operaciones tienen que realizar los algoritmos
para llegar a la solución, entre más operaciones se hagan el caso es peor
Se Busca un promedio de operaciones que se realizan para la solución de un problema. Se considera todas las entradas posibles
con un tamaño determinado
El mejor caso, es aquel en el que el algoritmo utiliza la menor cantidad de recursos (tiempo, por ejemplo) para solucionar el
problema.
Se necesita analizar la potencia de los algoritmos independientemente de la
potencia de la máquina q lo vaya a ejecutar o la habilidad que tenga el programador.
Se describe pro medio de una función cuyo dominio son los
números naturales N
Complejidad Terminología O(1) Complejidad constante O(n2) Complejidad cuadrática O(log n) Complejidad logarítmica O(n) Complejidad lineal O(n log n) Complejidad casi-lineal O(n^b) Complejidad polinómicaO(b^n) Complejidad exponencial O(n!) Complejidad factorial