Unidad II Manejo de Memoria

Manejo de memoria

Todas las variables, arreglos y objetos en general tienen una duración determinada en el transcurso de un programa. Son creados y destruidos para su uso y después para que la memoria sea liberada para que la utilicen otros objetos.
En C# existen tres formas de usar la memoria para almacenar valores:

a) Memoria Estática: Es la utilizada por variables globales y las declaradas de tipo Static. Estos objetos tienen asignada la misma dirección de memoria desde el comienzo hasta el final del programa.

b) Memoria Automática: Es la utilizada por Argumentos en una función y por las variables locales. Cada entrada en la función crea estos objetos y son destruidos al salir de ella.

c) Memoria Dinámica: Es también llamado almacenamiento libre porque en este caso el programador es el que solicita memoria para crear los objetos y es el responsable de liberar la memoria cuando ya no la necesita para ser reutilizada.

La reserva y liberación para variables globales, estáticas, locales y argumentos son realizadas en forma implícita por el programa, la única que requiere intervención del programador es la reserva y liberación de memoria dinámica.

Manejo de memoria dinamica

-memoria dinamica:

La reserva de memoria dinamica se hace en tiempo de ejecucion despues de leer los datos de conocer el tamaño exacto del problema a resolver, como consecuencia se adapta mejor a las necesidades de cada caso pero en contrapartida es un poco mas dificil programar.Tanto la creacion como la construccion de los objetos esta en manos deñ programador a traves de los operadores new y delete, el sitio donde se almacenan los objetos suele denominarse heap o free store, traducido como monticulo o memoria libre. No es necesario considerar la liberacion de la memoria dinamica puesto que framework se encarga de liberar todas las referencias que no se esten usando y compactar la memoria para mejorar el rendimiento.

Tipos valo en c#
*tipos predefinidos(int, float...)
*Estructuras(struct)
*Enumeraciones(enum)

Tipos-referencia en c#
*objetos
*string
*todas las clases

En c# todas las clases son tratadas sintacticamente como referencias y no permite elegir como reservar memoria par un instante en particular, en cambio obliga a que un valor int entero sea un tipo valor siempre.

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