Medida del uso de los recursos computacionales requeridos por la ejecución de un algoritmo en función del tamaño de las entradas. La eficiencia de los algoritmos, principio de invariancia, operaciones con órdenes de complejidad, funciones anónimas, análisis de algoritmos, el caso especial de los algoritmos recursivos, análisis de los algoritmos de ordenación.
T(n) Tiempo empleado para ejecutar el algoritmo con una entrada de tamaño n
Tipos de análisis
¿Cómo medimos el tiempo de ejecución de un algoritmo?
- Mejor caso
En condiciones óptimas (no se usa por ser demasiado optimista).
- Peor caso
En el peor escenario posible (nos permite acotar el tiempo de ejecución).
- Caso promedio
Caso difícil de caracterizar en la práctica.
- Análisis probabilístico
Asume una distribución de probabilidad sobre las posibles entradas.
- Análisis amortizado
Tiempo medio de ejecución por operación sobre una secuencia de ejecuciones sucesivas.
Ejemplo
- Algoritmo 1: T(n)
10-4 2n segundos= n
38 datos= T(n)
1 año= - Algoritmo 2: T(n)
10-2 n3 segundos= n
1000 bits= T(n)
Orden de eficiencia
Un algoritmo tiene un tiempo de ejecución de orden f(n), para una función dada f, si existe una constante positiva c y una implementación del algoritmo capaz de resolver cada caso del problema en un tiempo acotado superiormente por c•f (n), donde n es el tamaño del problema considerado.
EJEMPLOS
int fact(int n)
{
if (n <= 1)
return 1;
else
return (n * fact(n – 1));
}
int E(int n)
{
if (n == 1)
return 0;
else
return E(n/2) + 1;
}
public class Prueba
{
public static void main (String[] args) {
int[] a=new int[30000];
int[] res;
Secuencia sec= new Secuencia(a);
System.out.println("Inicio");
res=sec.subsecuenciaSumaMaxima3();
System.out.printf("Resultado 3={%d,%d}%n",res[0],res[1]);
res=sec.subsecuenciaSumaMaxima2();
System.out.printf("Resultado 2={%d,%d}%n",res[0],res[1]);
res=sec.subsecuenciaSumaMaxima1();
System.out.printf("Resultado 1={%d,%d}%n",res[0],res[1]);
System.out.println("Final");
}
}