Seleccion de un algoritmo

Cuando se resuelve un problema y se tiene que elejir entre varios algoritmos los siguientes dos objetivos suelen contradecirse.

1. Que el algoritmo sea facil de entender, codificar y depurar.
2. Que el algoritmo use eficientemente los recursos de la computadora y se ejecute con la mayor rapidez posible.

En conclusion cuando se escribe un programa que se va ha usar una o pocas veces el primer punto sera el mas importante y por lo contrario cuando se presenta un problema cuya solucion se va ha utilizar muchas veces el segundo punto sera el mas importante. Desde el punto de vista economico realizar un algoritmo complejo es util siempre que el tiempo de ejecucion sea significativamente menor que el de un programa mas sencillo.

Complejidad en el espacio

Es la memoria que utiliza un programa para su ejecución; es decir el espacio de memoria que ocupan todas las variables propias del algoritmo.

Esta se divide en Memoria Estática y Memoria Dinámica.

Memoria estática. Para calcularla se suma de memoria que ocupan las variables declaradas en el algoritmo.

Memoria dinámica. Su cálculo no es tan simple ya que depende de cada ejecución del algoritmo.

Ejemplo: algoritmo de búsqueda en arboles.

Función búsqueda_arboles.

Devuelve una solución o fallo.

Inicializa un árbol de búsqueda con estado inicial.

Bucle hacer

- Si no hay candidatos para expandir.

- Entonces devolver fallo.

- En otro caso escoger nodo para expandir.

- Si el nodo es el objetivo.

- Entonces devolver solución.

- En otro caso expandir nodo.

M = profundidad máxima del árbol (puede ser infinita)

D = profundidad de la mejor solución (menor costo)

B = factor de ramificacion (numero máximo de sucesiones) = 10

Depth	Nodes	Time	Memory
0	1	1 milisecond	100 bytes
2	111	.1 second	11 Kb
4	11111	11 second	1 Mb
6	1000000	18 minutos	111 Mb

Reglas para calcular la complejidad de un algoritmo

1. Sentencia sencilla:
Se refiere a las sentencias de asignacion de entrada y salida de datos, siempre y cuando no se trate de variables estructuradas cuyo tamaño esta relacionado con n. Requiere un tiempo constante de ejecucion siendo su complejidad O(1).

2. Secuencia de sentencias:
La complejidad de una serie de instrucciones de un programa sea delorden de la suma de las complejidades individuales dependiendo de las intrucciones que se traten.

3.Decision (if, switch):
La condicion if suele ser de complejidad constante sumando la peor rama posible ya sea en el then o en el else, la desicion multiple o switch tomara la peor de las ramas en todos los casos.

4. Bucles (ciclos):
En los bucles con contador explicito como el for se tienen dos casos que el tamaño de N forme parte del limite del ciclo o no.

a) N forma parte limite ciclo
for (int i=0; i N * O(1) = 0(n) complejidad Lineal

b) N no forma parte del limite del ciclo
for (int i=0l; i K*O(1) = O(1) Complejidad Constante

5. Llamadas a procedimientos.
La complejidad de llamar a un procedimiento esta dado por la complejidad de las instrucciones del procedimiento en si, pudiendo complicarse notablemente si se trata de procedimientos recursivos.

Funcione factorial No recursiva

int factorial(int n) O(n1)
{
int fact=1;
for(int i=n;i>0;i--)
{
fact*=i;
}
return fact;
}

=>complejidad lineal O(n)

Ordenes de Complejidad

Se agrupan los algoritmos de acuerdo a la complejidad en el tiempo de ejecucion y se tienen los siguientes

1. O(1) Constante Funciones independientes del volumen de datos Ideal
2. O(n) Lineal Algoritmos que actuan sobre todos los elementos Eficiente
3. O(n Log n) Casi Lineal Bucles en los que cada paso implica un coste logaritmico Eficiente
4. O(log n) Logaritmico Algoritmos que descartan muchos valores en un unico paso Eficiente
5. (n'x) Polinomial Estructuras de datos lineales como vectores y en los bucles Tratable
   

1.3 Complejidad en el tiempo de Ejecucion

--> Ordenes de Complejidad
--> Reglas para calcular la complejidad de un algoritmo

Tiempo de ejecucion de un programa en funcion de N se puee medir fisicamente con un reloj o calcularse sobre el codigo contando las instrucciones a ejecutar y mulplicandolas por el tiempo requerido por cada una de ellas.

Ejemplo:
S1
for(int i=0; is2;
requiere T(N)= t1+t2*N

Siendo T1 el tiempo que lleva ejecutar la sentencia S1 y T2 el tiempo que lleva ejecutar la sentencia 2 multiplicando por N.

1.2 Notacion aritmetica "O" grande

Se usa para el analisis de algoritmos mide la eficiencia de un algoritmo conforme crece el tamaño

Ejemplo: T(n)=CN
C -> Tiempo que lleva examinar una variable.

int maximo(int arreglo, int n)
{
int mayor=0;
for(int i=0; imayor)
mayor=arreglo[i];
return mayor;
}
}

Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion, ignora los valores constanteses decir no toma en cuenta si se hace una mejor o peor implementacion del algoritmo y es independiente de los datos de entrada al algoritmo su utilidad radica en encontrar un limite superior del tiempo de ejecucion es decir el peor caso.

Formula:
g(n) <= cf(n), para todo n>=n

Significa que existen constantes enteros positivos C y No , tales que para n>=No, se cumple la funcion

T(n)<=CN Ejemplo: Supongase que T(n)=(n+1)'2, No=1, C=4 verificar que se cumple la funcion para todo n>=1

• Programa 1: El orden de magnitud de la funcion es el orden del termino mas grande respecto de n (n+1)'2 <= 4(n)'2

T(2) (2+1)'2 <= 4(2)'2 9 <= 16

• Programa 2: Funcion T(n)= 3n'3 + 2n'2 + 10, cuando No=1 y C=5 , verificar para n>=1
  
  
  

U1-1.1Concepto de Complejidad

Unidad 1-Analisis de algoritmos

1.1Concepto de complejidad

Las respuestas posibles son Si o No se clasifican en conjuntos de complejidad comparable:

P: Es el conjunto de los problemas de decision que pueden ser resueltos en tiempo polinomico calculado en una maquina de Turing determinista, los cuales pueden ser resueltod aun en el peor de los casos. Ejemplos.

a)Saber si un numero es primo
b)Saber si cierta frase pertenece a un conjunto dado

NP: Es el conjunto de los problemas de decision que pueden ser resueltos en tiempo polinomico en maquina de turing, todos los problemas de esta clase tienen la propiedad de poder ser verificados, ejemplo.

a)Problema del agente viajero
b)Problema de satisfactibilidad booleana

NP Completo: es el subconjunto de problemas de decision en NP que destacan por su extrema complejidad y graficamente se encuentran en la frontera externa de la clase NP, ejemplo.

a)Suma de subconjuntos
b)Isomorfosis de grafos