Un programa, por muy correcta que sea su implementación, puede no ser viable(debido al tiempo que necesita para ejecutarse o por la cantidad de espacio que necesita) para algunos tipos de entrada. Cuando realizamos el análisis de un algoritmo nos refermios al proceso de estimación del tiempo y espacio necesarios para ejecutar el algoritmo. La complejidad de un algoritmo hace referencia a la cantidad de tiempo y espacio necesarios para ejecutar el algoritmo. Con la tecnología actual podemos decir que la memoria de las computadoras es abundante y barata, es por eso la complejidad del algoritmo se puede limitar al tiempo de ejecución del algoritmo.
El tiempo de ejecución dependerá del programa y de su entrada (carga de trabajo ).
Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo, es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
La eficiencia de un algoritmo está dada por el análisis del mismo, basándose en la dimensión temporal( tiempo empleado) y la dimensión espacial (recursos invertidos). Una buena estimación de la eficiencia debe ser independiente de aspectos de implementación (la plataforma y el lenguaje con que se codificará) pero debe reflejar sus diferencias.
La gran mayoría de los problemas tiene un parámetro de entrada que es el número de datos que se van a procesar, denominado comúnmente como N. La cantidad de recursos del algoritmo es tratada como una función de N.
Así, se establece un tiempo de ejecución del algoritmo que por lo general es proporcional a una de las siguientes funciones :
O (l) orden constante : La mayoría de las instrucciones se ejecutan muy pocas veces.
O (log n) orden logarítmico : Se puede considerar como una gran constante.
O (n) orden lineal : Tiempo de ejecución lineal (un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética.
O (nlog n) orden de nlogn : Si N se duplica el tiempo de ejecución es ligeramente mayor del doble. Un ejemplo de este algoritmo sería la búsqueda binaria ó dicotómica.
O (n2) Tiempo de ejecución cuadrático. Si n se duplica el tiempo de ejecución aumenta cuatro veces.
O (n3) Tiempo de ejecución cúbico. Si n se duplica el tiempo de ejecución aumenta ocho veces.
Los algoritmos de complejidad O (n) y O (n log n) son los que tienen un comportamiento más natural. prácticamente a doble de tiempo, doble de datos procesables.
Los algoritmos de complejidad logarítmica son un descubrimiento fenomenal, ya que en el doble de tiempo permiten resolver problemas mayores, y para resolver un problema el doble de grande sólo hace falta un poco más de tiempo (no muy significativo).
Se refiere a la medida del tiempo empleado. El tiempo de ejecución dependerá del programa y de su entrada (carga de trabajo).
El tiempo total para una función se puede determinar por el tiempo requerido para cada instrucción, multiplicado por las veces que se ejecutan.
Teniendo el siguiente código :
i=0
Mientras i <>
Se refiere a la medida de los recursos invertidos. Al hablar de complejidad en espacio se hace referencia a la memoria que utiliza un programa para su ejecución. La eficiencia de la memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo, es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
La cantidad de memoria necesaria para llegar a la solución del problema considera lo siguiente :
Si tenemos el código :
Mientras i <>falta 1.4 Selección de un algoritmo
Al hablar de manejo de memoria nos referimos a la forma en la que se trabaja con este recurso, al implementar estructuras de datos. Podemos hablar de memoria estática y memoria dinámica.
Empezaremos por definir el concepto de estructuras de datos
a) Es la forma en que están relacionados objetos de datos o datos complejos.
Las Estructuras de Datos son muy importantes en los sistemas de computadora, contienen los tipos de datos más frecuentes utilizados en los diferentes lenguajes de programación.
Se pueden definir los tipos de datos como simples y estructurados. Los datos simples o primitivos son los que no están compuestos de otras estructuras, por ejemplo :
Los datos Estructurados o compuestos (están construidos basados en tipos de datos primitivos por ejemplo cadena "string" varios caracteres) .
Las Estructuras de datos Dinámicas no tienen las limitaciones o restricciones en el tamaño de memoria ocupada que son propias de las estructuras estáticas. Mediante el uso de un tipo de datos específico denominado puntero, es posible construir estructuras de datos dinámicas que son soportadas por la mayoría de los lenguajes.
La elección del tipo de estructura de datos idónea a cada aplicación dependerá esencialmente del tipo de aplicación y en menor medida del lenguaje.
Característica que diferencia a los tipos de datos:
Los tipos de datos simples tienen como característica común que cada variable representa a un elemento. Los tipos de datos estructurados tienen como característica común que un identificador (nombre) puede representar múltiples datos individuales, pudiendo ser cada uno referenciado independientemente.
* Funciones para acceso
* Funciones destructuras
Se encargan de devolver al sistema los recursos asignados a la estructura de datos para que queden a disposición de éste. Esta forma es la más utilizada y normalmente no es necesario efectuar ninguna operación sobre la estructura; pues queda automáticamente liberado el espacio que ocupaba.
Operaciones más comunes sobre una Estructura de Datos
* Listas
Las operaciones elementales que se pueden realizar en una pila son:
Quitar un elemento (Pop)
Si TOPE <> 0
Hacer DATO <- PILA[TOPE]
Indirecta : Se da cuando un subprograma llama a otro programa y éste a su vez llama al primero. En toda definición recursiva de un problema se debe establecer un estado básico. Es decir un estado en el cual la solución no se presente de manera recursiva sino directamente. 
Estucturas de datos tipo cola
Una cola es una lista de elementos en la que éstos se introducen por un extremo y eliminan por el otro. Los elementos se eliminan en el mismo orden en el que se insertaron. Por lo tanto el primer elemento que entra a la cola será el primero en salir. Debido a esta característica, las colas también reciben el nombre de estructuras FIFO (First-In, First-Out: primero en entrar, primero en salir).
Existen numerosos casos de colas en la vida real : las personas esperando para usar un teléfono público, un cajero automático, los carros esperando la luz verde, los niños esperando para subir a un juego mecánico, etc.
Representación de colas
Arreglos
Listas Enlazadas.
Como en el caso de las pilas también se utilizarán arreglos. Debe definirse un tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que guarde la posición del primer elemento de la cola (FRENTE) y otra para que guarde la posición del último elemento de la cola (FINAL).
Tipos
Colas Simples
- Colas Circulares
- Colas Dobles
Colas Simples
Es una lista de elementos en la que éstos se introducen por un extremo y eliminan por el otro
Cola
MAX | ||
... | ||
... | ||
... | ||
FINAL | 4 | 444 |
3 | 333 | |
2 | 222 | |
FRENTE | 1 | 111 |
Cola Llena
FINAL y MAX | 999 | |
... | ||
... | ||
... | ||
4 | 444 | |
3 | 333 | |
2 | 222 | |
FRENTE | 1 | 111 |
Cola con algunos elementos
MAX | 999 | |
... | ||
... | ||
... | ||
4 | ||
FINAL | 3 | 333 |
2 | 222 | |
FRENTE | 1 | 111 |
Cola vacía
MAX | ||
4 | ||
3 | ||
2 | ||
1 |
FRENTE Y FINAL = 0
Operaciones con Colas
Insertar un elemento
Eliminar u n elemento
Las inserciones se llevarán a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE (recuerde que el primero en entrar es el primero en salir).
Considerando que una cola puede almacenar un máximo número de elementos y que además la posición del primer elemento está almacenada en FRENTE y la posición del último en FINAL, se presentan ahora los algoritmos de inserción y eliminación en colas.
INSERTACOLA ( COLA, MAX, FRENTE, FINAL, DATO)
1. Si FINAL< MAX
entonces
Hacer FINAL=FINAL+1
COLA[FINAL]=DATO
1.1 Si FINAL=1 entonces
Hacer FRENTE=1
1.2 Fin del paso 1.1
Si no
Escribir "Desbordamiento"
2. Fin del paso 1
ELIMINACOLA ( COLA, FRENTE, FINAL, DATO)
1. Si FRENTE<>0
entonces
Hacer DATO=COLA[FRENTE]
COLA[FRENTE]=0
1.1 Si FRENTE=FINAL entonces
Hacer FRENTE=0
FINAL=0
si no
Hacer FRENTE=FRENTE+1
1.2 Fin del paso 1.1
Si no
Escribir "Subdesbordamiento"
2. Fin del paso 1
Ejemplo
Se insertan en COLA los elementos: lunes, martes, miércoles, jueves y viernes ( en ese orden ), de modo que la estructura queda como se muestra en la figura:
Cola
MAX | 7 | |
6 | ||
FINAL | 5 | viernes |
4 | jueves | |
3 | miércoles | |
2 | martes | |
FRENTE | 1 | lunes |
Se elimina "lunes"
Cola
MAX | 7 | |
6 | ||
FINAL | 5 | viernes |
4 | jueves | |
3 | miércoles | |
FRENTE | 2 | martes |
1 |
Se inserta "Sábado"
Cola
MAX | 7 | |
FINAL | 6 | sábado |
5 | viernes | |
4 | jueves | |
3 | miércoles | |
FRENTE | 2 | martes |
1 |
Se eliminan "martes","miércoles","jueves","viernes"
Cola
MAX | 7 | |
FRENTE Y FINAL | 6 | sábado |
5 | ||
4 | ||
3 | ||
2 | ||
1 |
Se inserta "domingo"
Cola
FINAL | 7 | domingo |
FRENTE | 6 | sábado |
5 | ||
4 | ||
3 | ||
2 | ||
1 |
Se elimina "sábado"
Cola
FINAL y FRENTE | 7 | domingo |
6 | ||
5 | ||
4 | ||
3 | ||
2 | ||
1 |
Si se quisiera insertar un nuevo elemento ya no se podría, puesto que FINAL no es menor que MAX (FINAL=MAX=7). Sin embargo, como se ve en la última fig. hay espacio disponible.
Se llego a una situación conflictiva: a pesar de que hay espacio, no se pueden insertar otros elementos. Este incoveniente puede superarse manejando las colas como se muestran en el sig. punto.
Colas circulares
Para hacer un uso más eficiente de la memoria disponible se trata a la cola como a una estructura circular. Es decir, el elemento anterior al primero es el último.
COLA CIRCULAR
Fig. 1
XX | YY | ZZ | KK | TT | WW | RR | |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
FRENTE | FINAL |
COLA CIRCULAR
Fig. 2
ZZ | KK | TT | WW | RR | |||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
FRENTE | FINAL |
COLA CIRCULAR
Fig. 3
PP | ZZ | KK | TT | WW | RR | ||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
FINAL | FRENTE |
En las fig. 1 se ilustran como se actualizan los punteros FRENTE y FINAL en una cola circular, a medida que se insertan o eliminan elementos. La cola tiene algunos elementos (FRENTE=2 y FINAL=8). En la fig. 2 se han eliminado de la cola dos elementos (primero se quito XX y luego YY), quedando FRENTE=4. Por último, en la fig. 3 se ha insertado un nuevo elemento (PP) en la cola. Como FINAL= MAX se llevó el apuntador a la primera posición que estaba vacía ( FINAL = 1 ). De esta manera se logra un mejor aprovechamiento del espacio de memoria disponible, ya que al eliminar un elemento esa casilla de la cola queda disponible para futuras inserciones.
Algoritmo INSERTACIRCULAR
Insertacircular ( COLACIR, MAX, FRENTE, FINAL, DATO )
1. Si ((FINAL= MAX) y (FRENTE =1)) o ((FINAL+1)=FRENTE)
entonces
Escribir 'Desbordamiento' {La Cola está Llena}
Si no
1.1 Si FINAL=MAX
entonces
Hacer FINAL = 1
Si no
Hacer FINAL=FINAL+1
1.2 {Fin del condicional del paso 1.1
Leer DATO
COLACIR[FINAL]=DATO
1.3 Si FRENTE=0 entonces
Hacer FRENTE=1
1.4 {Fin del condicional del paso 1.3}
2. {Fin del condicional del paso 1}
Algoritmo ELIMINACIRCULAR
Eliminacircular ( COLACIR, MAX, FRENTE, FINAL, DATO )
1. Si FRENTE=0 {Verifica si la cola está vacía }
entonces
Escribir 'Subdesbordamiento'
Si no
Hacer DATO=COLACIR[FRENTE]
COLACIR[FRENTE]=0
1.1 Si FRENTE=FINAL {Si hay un sólo elemento}
entonces
Hacer FRENTE=0 y FINAL=0
Si no
1.1.1 Si FRENTE = MAX
entonces
Hacer FRENTE=1
si no
Hacer FRENTE=FRENTE+1
1.1.2 {Fin del condicional del paso 1.1.1}
1.2 {Fin del condicional del paso 1.1}
2. {Fin del condicional del paso 1 }
Doble Cola
Una doble cola o bicola es una generalización de una estructura de cola simple. En una doble cola, los elementos pueden ser insertados o eliminados por cualquiera de los extremos. Es decir, se pueden insertar y eliminar valores tanto por el FRENTE como por el FINAL de la cola. Una doble cola se representa como se muestra en la fig.
Las dos flechas en cada extremo indican que pueden ejecutarse las operaciones de inserción y eliminación.
Existen dos variantes de las dobles colas:
- Doble cola con entrada restringida
- Doble cola con salida restringida
La primera de ellas permite que las eliminaciones puedan hacerse por cualquiera de los dos extremos, mientras que las inserciones sólo por el final de la cola
La segunda variante permite que las inserciones puedan hacerse por cualquiera de los dos extremos, mientras que las eliminaciones sólo por el FRENTE de la cola.
Aplicaciones de colas
El concepto de cola está ligado a computación. Una aplicación de las colas puede verse en las colas de impresión. Cuando hay una sola impresora para atender a varios usuarios, puede suceder que algunos de ellos soliciten servicios de impresión al mismo tiempo o mientras el dispositivo está ocupado. En estos casos se forma una cola con los trabajos que esperan para ser impresos. Los mismos se irán imprimiendo en el orden en el cual fueron introducidos en la cola.
Otra aplicación sería el uso de colas en sistemas multiusuario y en sistemas de tiempo compartido.
Estucturas de datos tipo LISTA
Este tipo de estructura de datos dinámica está compuesta por un conjunto de nodos, generados a partir de un tipo de dato conocido con el nombre de puntero o de referencia. Un dato puntero almacena una dirección o referencia a un dato propiamente dicho. Por lo tanto, debe distinguirse claramente entre un dato puntero y el dato al cual éste apunta.
Se usará la notación P=^D para indicar que P es un puntero a datos de tipo D. Se genera un valor para una variable de tipo puntero cuando se asigna, dinámicamente, memoria a un dato apuntado por ella. Se usuará CREA(P) para indicar el proceso de asignación de memoria, y QUITA (P) para indicar el proceso inverso, es decir, cuando se libera una posición de memoria apuntada por P.
De esta manera se pueden crear estructuras dinámicas que se expandan o se contraigan, según se les agregue o elimine elementos.
Las variantes de listas se pueden clasificar como sigue:
Listas Simples
Una lista es una colección de elementos llamados generalmente nodos. El orden entre los nodos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos.
INFORMACION | LIGA |
En general, un nodo consta de dos partes:
- Un campo INFORMACION que será del tipo de datos que se quiera almacenar en la lista.
- Un campo LIGA, de tipo puntero, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. Si el nodo fuera el último de la lista, este campo tendra un valor NULL ( vacío ). Al emplearse el campo liga para relacionar dos nodos no será necesario almacenar físicamente a los nodos en espacios contiguos.
Ejemplo de una lista simple :
Las operaciones que se realizan con listas son:
- Recorrido de la Lista
- Inserción de un Elemento
- Borrado de un Elemento
- Búsqueda de un Elemento
Para realizar las operaciones anteriores debemos de crear la lista, a continuación se detalla el algoritmo para crear una lista al inicio
CREAINICIO(P)
{Este algoritmo crea una lista, agregando cada nuevo nodo al inicio de la misma}
{P y Q son variables de tipo puntero. P apuntará al inicio de la lista}
1.- CREA (P) {Crea el primer nodo de la lista}
2.- LEER P^.INFORMACION
3. HACER P^.LIGA<- NULL
4. REPETIR
CREA (Q)
LEER Q^.INFORMACION
HACER Q^.LIGA<- P y P<-Q
5. HASTA (que no haya información)
En java el código para crear al inicio sería algo así :
class nodo
{
int info;
nodo liga;
}
class creainicio
{
static nodo Q=null;
static nodo P=null;
public static void creaininodo()
{
int opc=1;
int dato;
if (P==null)
{
P=new nodo();
System.out.println("Dame Dato: ");
dato=TextIO.getlnInt();
P.info=dato;
P.liga=null;
}
do{
Q=new nodo();
System.out.println("Dame Dato: ");
dato=TextIO.getlnInt();
Q.info=dato;
Q.liga=P;
P=Q;
System.out.println("Otro nodo 1(SI) 2 (NO)");
opc=TextIO.getlnInt();
}while (opc!=2);
System.out.println("La Lista Creada es: ");
for (nodo i=P; i!=null; i=i.liga)
System.out.println("Campo Informacion: "+i.info+" Campo Liga: "+ i.liga);
}
public static void main (String args[])
{
System.out.println("Programa que Crea Inicio de Lista");
creaininodo();
System.out.println("Termina Programa que Crea Inicio de Lista");
}
}
CREAFINAL(P)
{Este algortimo crea una lista, agregando cada nuevo nodo al final de la misma}
{P y Q son variables de tipo puntero, P apuntará al inicio de la lista }
1.- CREA (P) { Crea el primer nodo de la lista}
2.- LEER P^.INFORMACION
3.- HACER P^.LIGA<- NULL y T <- P
4.- REPETIR
CREA (Q)
LEER Q^.INFORMACION
HACER Q^.LIGA <- NULL, T^.LIGA <- Q y T<- Q
5. HASTA (que no haya información)
En java el programa para crear al final sería :
class nodo
{
int info;
nodo liga;
}
class creafinal
{
static nodo Q=null;
static nodo P=null;
static nodo T=null;
public static void creafinnodo()
{
int opc=1;
int dato;
if (P==null)
{
P=new nodo();
System.out.println("Dame Dato: ");
dato=TextIO.getlnInt();
P.info=dato;
P.liga=null;
T=P;
}
do{
Q=new nodo();
System.out.println("Dame Dato: ");
dato=TextIO.getlnInt();
Q.info=dato;
Q.liga=null;
T.liga=Q;
T=Q;
System.out.println("Otro nodo 1(SI) 2 (NO)");
opc=TextIO.getlnInt();
}while (opc!=2);
System.out.println("La Lista Creada es: ");
for (nodo i=P; i!=null; i=i.liga)
System.out.println("Campo Informacion: "+i.info+" Campo Liga: "+ i.liga);
}
public static void main (String args[])
{
System.out.println("Programa que Crea final de Lista");
creafinnodo();
System.out.println("Termina Programa que Crea final de Lista");
}
}
El algoritmo requiere de otra variable puntero para mantener la dirección del último nodo de la lista, de tal manera que se pueda establecer el enlace entre éste y el nuevo nodo.
Recorrido de la lista
La operación de recorrido consiste en visitar cada uno de los nodos que forman la lista. La visita de un nodo puede definirse por medio de una operación muy simple ( por ejemplo la impresión de la información del mismo), o por medio de operaciones tan complejas como se desee.
Para recorrer todos los nodos de una lista se comienza con el primero. Tomando el valor del campo LIGA de éste se avanza al segundo; a su vez, el campo LIGA del segundo nos dará acceso al tercero y así sucesivamente. En general la dirección de un nodo, excepto el primero, está dada por el campo LIGA de su predecesor.
El algoritmo para recorrer la lista se puede hacer de forma iterativa o de forma recursiva.
RECORREITERATIVO(P)
{ Este algortimo recorre una lista cuyo primer nodo está apuntado por P }
{ Q es una variable de tipo puntero }
1.- HACER Q <- P
2.- REPETIR MIENTRAS Q<>NULL
ESCRIBIR Q^.INFORMACION
HACER Q <- Q^.LIGA {Apunta al siguiente nodo de la lista}
3. {FIN DEL CICLO DEL PASO 2}
Como las listas son estructuras de datos recursivas, pueden manejarse fácilmente con procesos recursivos.
RECORRERECURSIVO(P)
{ Este algortimo recorre una lista recursivamente. P es el apuntador al nodo a visitar}
1.- SI P<>NULL entonces
ESCRIBIR P^.INFORMACION
LLAMAR A RECORRERECURSIVO con P^.LIGA
{LLamada recursiva con el apuntador al siguiente nodo de la lista}
2. {FIN DEL CICLO DEL PASO 1}
|
INSERCION DE UN NODO ANTES/DESPUES QUE OTRO
El nuevo nodo se coloca antes (después) de otro nodo dado como referencia. Primero se analizará el caso precediendo a un nodo, y luego el de inserción sucediendo un nodo dado.
Algoritmo Insertantes
Hasta este momento en todas las operaciones de listas que hemos analizado, no se ha considerado algún orden entre los elementos. Si se supone que la lista está ordenada, en el momento de insertarle un nuevo valor, habrá que mantener el orden previamente establecido. Sin embargo, como los elementos están relacionados por medio de punteros esta operación (inserción manteniendo el orden) no tiene mayor costo ya que no se deben mover elementos.
A continuación se tratará sobre la operación de borrado (eliminación) de nodos de una lista. Como en el caso de la inserción, solo se considerarán listas desordenadas.
Borrado de un elemento
Consiste en quitar un nodo de la lista redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos en esta operación.
Eliminar el primer nodo
Eliminar el ultimo nodo
Eliminar un nodo con información X
Eliminar el nodo anterior/posterior al nodo con información X
a) ELIMINAR EL PRIMER NODO
Se quita el primer elemento de la lista, redefiniendo el valor del puntero al nuevo inicio de la misma. El proceso es muy sencillo.
se presenta un ejemplo de borrado del primer nodo de una lista aplicando el algoritmo anterior.
b) ELIMINAR EL ULTIMO NODO
Se quita el último nodo de la lista, redefiniendo a NIL el campo LIGA de su predecesor, Para alcanzar el último nodo se deberá recorrer previamente toda la lista, excepto si se usara un puntero indicando el final de la misma. a continuación se presenta un algoritmo de solución, considerando que solamente se tiene un puntero al inicio de la lista.
Borrado del último nodo de una lista
c) ELIMINAR UN NODO CON INFORMACION X
Se debe buscar al nodo que contenga la información dada como referencia (X) y eliminarlo, estableciendo la liga correspondiente entre su predecesor y su sucesor.
borrado de un nodo con información X
d) ELIMINAR EL NODO ANTERIOR (O POSTERIOR) AL NODO CON INFORMACION X
Dado un nodo como referencia se debe eliminar su predecesor o su sucesor, según el caso, estableciendo las ligas correspondientes. Aquí se tratará el caso del nodo predecesor.
Ejemplo de borrado del nodo predecesor de un nodo dado, aplicando el algoritmo anterior
Búsqueda de un elemento
La operación de búsqueda de un elemento en una lista se realiza de modo secuencial. Se deben recorrer los nodos, tomando el campo LIGA como puntero al siguiente nodo a visitar. Debido a esto se puede decirse que esta operación esta implícita en alguno de los casos de inserción y borrado.
Al igual que el caso de las operaciones vistas anteriormente, existe diferencia en el algoritmo según sea para trabajar con listas desordenadas o con listas ordenadas. Se comenzara con el algoritmo de búsqueda para listas desordenadas.
Para la búsqueda ordenada se hace una pequeña modificación en la condición del paso 2 para poder buscar en una lista ordenada de forma ascendente.
Todos los algoritmos aquí mostrados pueden ser implementados de manera recursiva ya que las listas en sí son estructuras recursivas por excelencia.
|
0 comentarios:
Publicar un comentario