Seleccion de un algoritmo

Cuando se resuelve un rpoblema y hay la necesidad de elegir entre varios algoritmos que nos puedan dar un resultado, existen dos objetivos que suelen contradecirse para elegir uno:
a) Que el algoritmo se afacil de enternder, codificar y depurar.
b) Que el algoritmo use eficientemente todos los recursos de la computadora y se ejecuta con la mayor rapidez posible.

El primer punto se debe elegir cuando se escribe un programa que se va a usar una o pocas veces ya que el costo del tiempo del programa no se da tan reelevante ya que solo se ejecutaa en pocas ocaciones.
El punto b es mas importante cuandos e presenta un problema cuya solucion se va a usar muchas veces, ya que el costo de ejecucion del programa minimizara al costo de escritura.
En conclusion siempre sera mas ventajoso (desde el punto de vista economico) tener un algoritmo complejo siempre y cuando el tiempo de ejecucion del rpograma sea significativamente menor.

Complejiad en el espacio

Complejidad espacial:
Es la memoria que utiliza un programa para su ejecución. Lo que implica que su eficiencia y memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo, es decir, espacio en la memoria que ocupan todas las variables propias del algoritmo.

Ejemplo:
Algoritmo de busqueda en arboles
Función búsqueda_arboles(problema)
Devuelve solución/fallo
Inicializa árbol de búsqueda con estado inicial
Ciclo hacer
Si no hay candidatos para expandir
Entonces devolver fallo
En otro caso escoger nada para expandir
Si el nodo es el objetivo
Si
Entonces devolver solución
En otro caso expandir nodo

1.3.1 Tiempo de ejecución de un algoritmo.

¿Cómo se mide el tiempo de ejecución de un programa en función de N (numero de datos)?
Esta función se puede medir físicamente calculando con un reloj o se puede calcular sobre el código contando las instrucciones o ejecutar y multiplicándolo por el tiempo requerido por cada instrucción.

Reglas practicas para calcular la complejidad de un algoritmo
1.- Sentencia sencilla: se requiere la sentencia de asignación, entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N (número de datos). Como requiere un tiempo constante de ejecución, su complejidad s de orden O (1).
2.- Secuencia de sentencias: su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencia que se trate, tomándose n cuenta el orden más alto.
3.- Decisión (if): la solución sele ser de orden constante O (1), sumando en la peor rama posible ya sea la de then o else.
4.-Bucles (ciclos): a) en los ciclos con contador explicito existen dos casos que el tamaño N forme parte e los limites del ciclo o no.
Ej. Caso 1:
For (int i=0; i{S1;}
Entonces K*0=O (1) constante
Caso 2:
For (int i=0; i>N; i++)
{S1;}
Entonces N*O (1)=O(n) Lineal

b) Evolución de variable DE CONTROL NO LINEAL (WHILE)
En los ciclos multiplicativos como while y do while el incremento o decremento de la variable de control no es lineal, lo que hace incrementar el orden de complejidad como en:
Ejemplo:
C=1; //incremento
While(c{
S1;
C=2*C;
}
Entonces complejidad O (log n) Logarítmica.
Ejemplo:
C=n; //decremento
While(c>1)
{S1;
C=c/2;
}
Complejidad O (log n)

5.- Llamadas a procedimientos: la complejidad de llamar a un procedimiento esta dada por la complejidad del contenido del procedimiento en si, es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el cuerpo del procedimiento. En conclusión la complejidad de un procedimiento tiende a complicarse si se trata de procedimiento recursivos.
Ejemplo:
Función factorial (no recursiva)
int factorial (int n)//sentencia entrada O (1)
{
int fact=1; //sentencia asignación O(n)
for (int i=0; 1>O; i--)// ciclo contador explicito O(n)
fact=fact*i; //sentencia de asignación O (1)
Return fact; //sentencia salida O (1)
}
Entonces: complejidad lineal O(n) por el ciclo for o numero de iteraciones igual a n.
ORDENES DE COMPLEJIDAD
O (1) Constante ideal
O(n) Lineal eficiente
O (log n) Logarítmico eficiente
O(n log n) casi logarítmico eficiente
O(n^k) polinomial tratable
O (K^n) Exponencial intratable
O (n!) Factorial ingtratable

NOTACION ASINTOTICA OMEGA GRANDE

La funcion omega grande se usa para especificar una cota inferior para la velocidad de crecimineto de una funcion f(n) cuando esta en funcion de n. Y se usa la notacion:

T(n) es que se lee T(n) es omega grande de g(n) para un numero infinito de valores de n.


Ejemplo: Verificar la funcion para todos los valores n>=0
1+2>=1+3>=1

Aritmetica de la notacion O

*Notacion asintotica "O" grande: se usa para hacer referencia a la velocidad de crecimiento de los valores de una funcion. La utilidad de aplicar esta notacion a un algoritmo es encontrar el limite superior del tiempo de ejecucion, es decir, el peor caso.
=Definicion= |g(n)|<=|c.f(n)|, para todo n>n0.

Esto signofica que la funcion g(n) pertenece o es valida para f(n) si i solo si existen las constantes c y n0 tales que para n>=n0 T(n)<=cn

El orden de magnitud de la funcoin sera el orden del termino de la funcion mas grande respecto de n.

Ej. 1: Suponga que T(n)=(n+1)al cuadr cuando n0=1 y c=4 para n>=1. Verifique la funcion usando la "O" grande.
(n+1)2 <=cn2
(1+1)2<=4(1)2
2~2<4
4<=4

Existe una notación similar para indicar la mínima cantidad de recursos que un algoritmo necesita para alguna clase de entrada. La cota inferior de un algoritmo, denotada por el símbolo Ω, pronunciado “Gran Omega” u “Omega”, tiene la siguiente definición:

• T(n) está en el conjunto Ω (g(n)), si existen dos constantes positivas c y n0 tales que
|T(n)| ≥ c|g(n)| para todo n > n0.
• Ejemplo: Si T(n)=c1n2+c2n para c1 y c2 > 0, entonces:
|c1n2+c2n|≥|c1n2|≥c1|n2|
Por lo tanto, T(n) está en
Ω(n2).