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).

Teoria de complejidad computaional

Concepto de complejidad de algoritmo
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el cálculo para resolver un problema.
Estos recursos son: el tiempo y el espacio.
-Clases de complejidad.
Los problemas de decisión (aquellos donde las respuesta es si o no) se clasifican en conjunto de complejidad comparable que son llamados clases de complejidad.
a) Clase de complejidad P: Es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomio por una maquina de turins lo que corresponde a problemas que pueden ser resueltos aun en el peor de los casos
Ej. Camino optimo de un cartero, saber si un número entero es primo, decidir si una frase pertenece a un conjunto dado de frases.
b) Clase de complejidad NP: conjunto de los problemas de decisión que pueden ser determinados por una maquina de turins no determinista en tiempo polinomio. Los problemas de esta clase tienen la propiedad de que su solución puede ser verificada.
Ej. El problema del agente viajero, El problemas de satisfacción booleana.
c) Clase de complejidad NP-Completo: Es el subconjunto de los problemas de decisión de Np que destacan por su extrema complejidad y que decimos que se hayan en la frontera externa de la clase NP.
Ej. La suma de subconjuntos dado un conjunto S de enteros, ¿existe un subconjunto no dado cuyos elementos sumen 0?, ¿Dos grafos son isomórficos si se puede transformar uno en el otro simplemente renombrando sus vértices?

¿Las clases P y Np son diferentes o no?
El Clay Mathematics Institute ofrece 1 millón de dólares a quien sea capaza de responder satisfactoriamente a esa pregunta.