BD I - Capítulo 4. Álgebra Relacional: INTERSECT

Siguiendo con el álgebra relacional, estudiaremos en qué consiste la operación INTERSECT.

El resultado de esta operación es una relación que contiene las tuplas comunes a las dos relaciones intervinientes.

Sean las relaciones R = {A, B} y S = {A,B}

R

A	B
a1	b1
a2	b2

S

A	B
a1	b1
a3	b3

Al igual que como ocurría con la UNION, las cabeceras de ambas relaciones deben ser idénticas.

La intersección de ambas da como resultado

R INTERSECT S

A	B
a1	b1

Vemos que la relación resultante sólo contiene una tupla. Esta tupla es la que existía tanto en la relación R como la relación S.

Para mayor claridad, veamos un ejemplo más concreto. Tenemos las relaciones Personas = {Nombre, Apellido, Edad} y Gente = {Nombre, Apellido, Edad}

Ambas poseen la misma cabecera con lo cual es factible que apliquemos la operación de intersección.

Personas

Nombre	Apellido	Edad
Juan	Fernandez	34
Jose	Gonzalez	12
Martin	Perez	52
Carlos	Alvarez	25

Gente

Nombre	Apellido	Edad
Oscar	Juarez	22
Jose	Gonzalez	24
Martin	Perez	52
Carlos	Alvarez	25

El resultado se puede apreciar a continuación

Personas INTERSECT Gente

Nombre	Apellido	Edad
Oscar	Juarez	22
Jose	Gonzalez	24

BD I - Capítulo 3. Álgebra Relacional: UNION

Comenzaremos nuestro estudio del Álgebra Relacional con la operación UNION

El resultado de esta operación es una relación que contiene todas las tuplas de las relaciones intervinientes en la operación.

Sean las relaciones R = {A, B} y S = {A, B} que visualizamos a continuación

R

A	B
a1	b1
a2	b2

S

A	B
a1	b1
a3	b3

Estas son dos relaciones distintas pero que tienen exactamente la misma cabecera, es decir, están compuestas por los mismos atributos. Para poder realizar la operación el dominio de los atributos debe ser el mismo.

R UNION S da como resultado la siguiente relación

R UNION S

A	B
a1	b1
a2	b2
a3	b3

Podemos ver que contiene todas las tuplas de R y todas las tuplas de S. Además, la tupla (a₁, b₁) sólo aparece una vez.

Se puede apreciar la similitud entre la unión de relaciones y la unión de conjuntos. Esto se debe a que el álgebra relacional está basada en la teoría de conjuntos.

Veamos ahora un ejemplo más concreto. Sea la relación Personas = {Nombre, Apellido, Edad} y la relación Gente = {Nombre, Apellido, Edad}.

Ambas poseen la misma cabecera y el dominio de sus atributos es idéntico. Por lo tanto podemos llevar a cabo la UNION.

Personas

Nombre	Apellido	Edad
Juan	Fernandez	34
Jose	Gonzalez	12
Martin	Perez	52
Carlos	Alvarez	25

Gente

Nombre	Apellido	Edad
Oscar	Juarez	22
Jose	Gonzalez	24
Martin	Perez	52
Carlos	Alvarez	25

El resultado se ve en la siguiente tabla

Personas UNION Gente

Nombre	Apellido	Edad
Juan	Fernandez	34
Jose	Gonzalez	12
Martin	Perez	52
Carlos	Alvarez	25
Oscar	Juarez	22
Jose	Gonzalez	24

BD I - Capítulo 2. Modelo Relacional

La intención de este capítulo es introducir la notación que será utilizada en capítulos posteriores.

El modelo relacional es un modelo matemático abstracto que trabaja con relaciones, definiendo sus propiedades. El álgebra relacional es la que se encarga de definir las operaciones entre relaciones.

Para nosotros, existirá una equivalencia entre relación y tabla. Utilizaremos tablas para representar las relaciones y facilitar su estudio.

Sea la relación R = {A, B, C, D}

Donde R es el nombre de la relación y tanto A, B, C, D son los atributos que la componen.

Ya que dijimos que hablaremos de relaciones y tablas en forma equivalente, veamos cómo representar la estructura de la relación R en una tabla.

R

A	B	C	D
a1	b1	c1	d1
a2	b2	c2	d2
a3	b3	c3	d3
...	...	...	...
an	bn	cn	dn

Vayamos descomponiendo cada uno de los elementos que conforman a la relación R. En primera instancia vemos una cabecera

R

A	B	C	D

Esta cabecera está compuesta de metadatos, son los nombres que recibe cada atributo. En este caso tenemos los atributos A, B, C y D.

Los atributos poseen las siguientes propiedades:

• Identificador. Es decir, tienen un nombre único
• Atómico. Los atributos son indivisibles.
• Dominio. Define los valores legales y las operaciones que puede realizar cada atributo.

Cada fila de la relación R recibe el nombre de tupla. Cada tupla tiene los valores correspondientes a los atributos. Así, la primera tupla de la tabla es la siguiente:

a1

b1

c1

d1

Otros conceptos asociados a la estructura de una relación son los siguientes:

• Cuerpo. Es el conjunto de tuplas, el conjunto de todas las filas de la tabla (exceptuando la cabecera).
• Cardinalidad. Es la cantidad total de tuplas de la relación.
• Grado. Es la cantidad total de atributos.

 

De esta forma, la relación R tiene un grado igual a 4 y una cardinalidad igual a 'n'.

BD I - Capítulo 1. Introducción

Base de Datos I

Damos inicio al estudio de una nueva asignatura. No es la intención del curso focalizarse en conceptos teóricos, preferimos dejarle ese aspecto a autores como Date, Elmasri y Navathe.

Solamente a modo de introducción diremos que una Base de Datos es un conjunto de datos almacenados entre los que existen relaciones lógicas y que ha sido diseñada para satisfacer los requerimientos de información de una determinada empresa u organización.

Todos los contenidos que estudiaremos en los capítulos siguientes corresponderán al modelo de datos relacional. Cuando decimos modelo de datos nos referimos a que deben describirse:

• Estructuras de datos: Son los tipos de datos que existen en la base y la forma en que se relacionan.
• Restricciones de integridad: Condiciones que deben cumplir los datos para reflejar correctamente la realidad.
• Operaciones de manipulación de datos: Básicamente operaciones de inserción, eliminación, modificación y recuperación de datos.

En particular, las Bases de datos relacionales modelan la realidad utilizando relaciones. Estas relaciones pueden considerarse en forma lógica como conjuntos de datos. Pensamos cada relación como tablas compuestas por registros (las filas de la tabla) y campos (las columnas de la tabla).

Los temas que iremos abordando en los próximos capítulos son:

• Álgebra Relacional
• SQL
• Dependencias Funcionales
• Normalización de Base de Datos 

Capítulo 21. Algoritmos Greedy: Ejemplo de la mochila (Parte III)

Realizamos una ligera modificación al pseudocódigo del algoritmo de la mochila para poder almacenar los elementos que forman parte de la solución y devolverlos como resultado

Pseudocódigo

Análisis de Complejidad Temporal

El análisis es idéntico al realizado para el algoritmo del capítulo previo. La complejidad queda en el orden O(n*log(n)) si utilizamos MergeSort para ordenar la cadena por la razón Beneficio/Peso.

Capítulo 20. Algoritmos Greedy: Ejemplo de la mochila (Parte II)

Presentamos el pseudocódigo del ejemplo que resolvimos manualmente en el capítulo anterior.

Pseudocódigo

Análisis de Complejidad Temporal

Cabe señalar una importante diferencia respecto del análisis temporal para el ejemplo del cambio. Fijemos nuestra atención en el bloque 'mientras' y las condiciones:

i <= longitud(S) y capacidadParcial < P

En el peor de los casos, el bloque se ejecutará 'n' veces, siendo 'n' la cantidad de elementos en la secuencia S. Es decir, tiene mayor peso la condición i <= longitud(S) que la condición capacidadParcial < P.

Esto es así debido a que los objetos son finitos y no pueden repetirse en el armado de la solución final. Distinto era el caso en el ejemplo del cambio donde teníamos instancias infinitas de cada moneda y el objetivo era cubrir un importe P.

 

Las sentencias contenidas en el bloque 'mientras' tienen una complejidad constante dando un costo de O(n) para todo el bloque por lo explicado anteriormente.

Se observa entonces que la complejidad temporal del algoritmo dependerá del método de ordenamiento elegido para "ordenarPorBeneficioPeso". Si utilizamos MergeSort la complejidad temporal de MOCHILA_GREEDY nos queda en O(n*log(n)).

No debe sorprendernos que la complejidad en algoritmos Greedy venga dada por el método de ordenamiento utilizado ya que es la forma más eficiente que encontramos para implementar la estrategia de selección.

En el próximo capítulo haremos una ligera modificación al pseudocódigo de forma que nos permita guardar los elementos que serán almacenados en la mochila.

Fuentes:

Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda

Capítulo 19. Algoritmos Greedy: Ejemplo de la mochila (Parte I)

Continuando con los Algoritmos Greedy, centraremos nuestra atención en el ejemplo de la mochila. La descripción del problema es la siguiente:

Se tienen n objetos y una mochila con capacidad P. Cada uno de los n objetos tiene dos propiedades: peso y beneficio. Para i = 1, 2, ..., n, el objeto i tiene un peso p_i y un beneficio b_i. Tanto el peso como el beneficio son siempre positivos.

Además, los objetos pueden ser fraccionados, esto quiere decir que puedo llevar 1/2, 1/3 o cualquier otra fracción de un objeto.

Matemáticamente si una fracción x_i (0<x_i<1) del objeto i es colocada en la mochila, esta fracción contribuye en un peso x_i*p_i y en un beneficio x_i*b_i.

Para dejar en claro esto último, si tengo un objeto i cuyo peso es 12 y beneficio es 9, si decido llevar 1/3 del objeto, la contribución de este objeto al problema sería:

Peso = x_i*p_i = 1/3*12 = 4. 
Benefición = x_i*b_i = 1/3*9 = 3. 

Aclarado todo esto, el objetivo del problema es llenar la mochila de forma tal que se maximice el beneficio de los objetos transportados sin exceder la capacidad P (peso total) de la mochila.

Vamos a resolver un ejemplo de este problema en forma manual y en el siguiente capítulo lo haremos a través del pseudocódigo. Supongamos entonces que tenemos la siguiente instancia del problema:

La capacidad P de la mochila es 12 y poseemos el conjunto de elementos:

Elementos = { (p = 5; b = 4) , (p = 7; b = 5), (p = 2; b = 3), (p = 6; b = 3), (p = 4; b = 5) }

Con el fin de abreviar la nomenclatura representaremos a cada elemento e_i con el par (p_i, b_i). De esta forma, el conjunto anterior es simplemente:

Elementos = { (5,4), (7,5), (2,3), (6,3), (4,5) }

Recordemos que en los algoritmos Greedy podía identificarse una función selección, muchas veces asociada a la forma de ordenar el conjunto de elementos candidatos. En forma intuitiva, ya que el objetivo es maximizar el beneficio y los objetos pueden fraccionarse, convendría ordenar los elementos por su relación beneficio/peso en forma decreciente. Así, el conjunto de elementos ordenado por b/p nos queda:

Elementos = { (2,3), (4,5), (5,4), (7/5), (6, 3) }

Ahora, deberíamos ir tomando cada uno de estos elementos y verificar que no nos excedamos de la capacidad P de la mochila. Llamaremos W al peso parcial y B al beneficio parcial tras la elección de cada elemento (actúan como contadores).

Empecemos entonces tomando el primer elemento del conjunto ordenado, el (2,3). Nuestros contadores quedan:

W = 2
B = 3

Ya que no nos excedimos de la capacidad P, procedemos a elegir el siguiente elemento (4, 5):

W = 2 + 4 = 6
B = 3 + 5 = 8

Siendo que 6 es menor a P = 12 elegimos un tercer elemento, el (5,4):

W = 6 + 5 = 11
B = 8 + 4 = 12

El peso parcial acumulado aún no excede la capacidad de nuestra mochila, es por ello que podemos elegir un nuevo elemento: el (7,5).

W = 11 + 7 = 18 
B = 12 + 5 = 17

¿Qué ha pasado? Hemos superado la capacidad total P de la mochila. Siendo que el peso acumulado W del paso anterior era igual a 11, sólo necesitábamos contribuir en 1 para alcanzar la capacidad total. Aquí es cuando debemos fraccionar el elemento.

Es fácil ver que con la fracción 1/7 cumpliremos nuestro cometido y los acumuladores quedarán:

W = 11 + 1/7*7 = 12
B = 12 + 1/7*5 = 89/7

Todo esto realizado en forma intuitiva deriva en la solución óptima. Vale aclarar que debería demostrarse matemáticamente, cosa que excede el alcance de nuestro curso.

Esto mismo que hemos hecho manualmente, se verá plasmado en pseudocódigo en el siguiente capítulo.

Capítulo 18. Algoritmos Greedy: Ejemplo del cambio

En este y capítulos posteriores iremos analizando distintos ejemplos de aplicación de la técnica de algoritmos Greedy. Comenzaremos con estudiar el más sencillo de todos: el problema del cambio.

Se desea encontrar la forma de devolver un vuelto de valor 'v' con monedas de denominaciones d₁, d₂, ..., d_n considerando que existe una cantidad infinita de monedas de cada denominación.

Por ejemplo, queremos devolver $1.83 y disponemos de monedas de 1, 5, 10, 25, 50 centavos y 1 peso. La forma más sencilla e intuitiva de hacerlo es con una moneda de 1 peso, una moneda de 50 centavos, una moneda de 25 centavos, una moneda de 5 centavos y tres monedas de 1 centavo.

Esto que hacemos en forma intuitiva (devolver la cantidad pedida con la menor cantidad posible de monedas) puede expresarse en el siguiente algoritmo:

Cómo se estudió en el capítulo 16, debería ser posible identificar las 4 funciones que caracterizan a los algoritmos Greedy.

Así, el conjunto de candidatos es el conjunto de monedas disponibles y se dispone de infinitas monedas de cada denominación. El conjunto de candidatos pendientes viene dado por las posiciones mayores o iguales a i en la cadena 'monedas'.

La función selección es la que elige el elemento de la posición i sumado a que las monedas están ordenadas de mayor a menor (se indicó como 100 la moneda de 1 peso para diferenciarla de la moneda de 1 centavo).

La función de factibilidad es la que pregunta si s + monedas[i] < v (es decir, está preguntando si al sumarle el candidato elegido en ese momento al vuelto parcial 's', no nos estamos pasando del valor v a devolver).

La función solución es la que evalúa s < v y la función objetivo, implícita, es la que minimiza la cantidad de monedas.

Debemos tener en cuenta que este algoritmo es correcto para las denominaciones de monedas utilizadas. Para otras instancias del problema el algoritmo deja de ser óptimo y es necesario emplear otra técnica distinta que estudiaremos más avanzado el curso.

Para ilustrar este hecho supongamos que nuestra cadena de monedas es = [6, 4, 1] y se nos pide devolver un cambio de 8.

El algoritmo presentado en este capítulo nos daría el vuelto con una moneda de 6 y dos monedas de 1 (totalizando 3 monedas) cuando intuitivamente podemos apreciar que la manera más óptima sería devolver dos monedas de 4.

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 17. Algoritmos Greedy (Parte II)

Presentaremos en este capítulo la forma general en formato pseudocódigo de los algoritmos Greedy.

GREEDY
Entrada: C -> conjunto de candidatos.
Salida:  S -> solución del problema.

     mientras C <> vacío y no esSolucion(S)
          x <- Seleccionar(C)
          C <- C\{x}          
          si esFactible(S U {x})
              S <- S U {x} 
          fin si
     fin mientras
     si esSolucion(S) 
         devolver S
     fin si
     sino 
         devolver No hay solución
     fin si
fin GREEDY

Al tratarse de operaciones entre conjuntos vale aclarar la notación:

• C\{x} quiere decir que al conjunto de candidatos C se le quita el elemento x (ya que 'x' había sido seleccionado en el paso anterior).
• S U {x} significa que al conjunto de solución se le agrega el elemento x.

En los siguientes capítulos nos dedicaremos a estudiar ejemplos de aplicación de esta técnica de diseño de algoritmos.

Capítulo 16. Algoritmos Greedy (Parte I)

Características de los Algoritmos Greedy

 

La técnica de diseño de algoritmos denominada Greedy (algoritmos voraces) es aquella que va construyendo la solución de un problema a partir de decisiones parciales tomadas en base a la información disponible en cada momento.

 

No mira hacia adelante, es decir, no ve los efectos de las decisiones tomadas a futuro y nunca reconsidera una decisión ya tomada.

 

Esta técnica es utilizada en general para resolver problemas de optimización. Suelen ser muy eficientes pero su eficacia debe ser validada, o sea, debe tenerse mucho cuidado con su correctitud. Esto quiere decir que se debe demostrar que la solución encontrada es óptima.

 

Se basa en un conjunto de candidatos a formar parte de la solución. En cada paso se toma uno de los candidatos, el más apropiado y se evalúa si sirve o no. Si sirve, el candidato es agregado a la solución, caso contrario es descartado. Para ello, es necesario saber en todo momento, dado un candidato, si el mismo está pendiente de ser evaluado, si ya fue evaluado y agregado a la solución o si fue descartado.

 

Para cumplir con esto deben conocerse cuatro funciones:

• La función selección que es la que selecciona el mejor candidato dentro de los pendientes.
• La función factibilidad que evalúa si un candidato seleccionado es factible de formar parte de la solución.
• La función solución que evalúa si un conjunto solución propuesto conforma la solución al problema.
• La función objetivo que es la que se debe maximizar o minimizar (optimizar).

 

En el próximo capítulo presentaremos el pseudocódigo de la forma general de los algoritmos Greedy. Tener en cuenta que, aunque las cuatro funciones mencionadas deben estar presentes en el diseño, no siempre es trivial la identificación de las mismas dentro del algoritmo.

Fuentes:

 

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 15. MergeSort dividiendo cadena en tres partes

Cuando aplicamos MergeSort en capítulos previos, siempre fuimos dividiendo la cadena de entrada en dos partes. ¿Qué pasaría si dividiéramos la cadena en tres o más partes? ¿Mejoraría la complejidad temporal? En este capítulo intentaremos dar respuesta a estas cuestiones.

Enunciado

Dada una cadena S de números enteros, ordenarla en forma creciente. Utilizar el método de ordenamiento Merge-Sort, pero dividiendo la cadena en 3 subcadenas y analizar el costo.

Pseudocódigo

Análisis de Complejidad Temporal

Considerando que el método UnirCadenasOrdenadas tiene un costo lineal O(n), podemos ver que la cantidad de llamadas recursivas es 3 al igual que la cantidad en que se divide la cadena. El resto de asignaciones y comparaciones tienen un costo constante.

Por lo tanto, tenemos que a = 3, b = 3 y k = 1

Siendo a = b^k ya que 3 = 3¹ el orden del algoritmo es O(n^k*log(n)) lo que finalmente se traduce en un costo de O(n*log(n))

 

Así acabamos de mostrar que el hecho de dividir la cadena en una mayor cantidad de partes no mejora la complejidad temporal de MergeSort. Podemos proceder análogamente en el caso que deseemos dividir la cadena de entrada en 4 o más partes y veremos que el resultado no se ve alterado.

Capítulo 14. Métodos de Ordenamiento: QuickSort (Parte II)

En el capítulo previo estudiamos el funcionamiento del método de ordenamiento QuickSort. Aquí presentaremos el pseudocódigo del algoritmo así como también realizaremos el análisis de complejidad temporal del mismo.

Pseudocódigo

QUICKSORT
Entrada: S -> secuencia de enteros.
Salida:  S -> la misma secuencia ordenada.

     si longitud(S) > 1
          p <- pivot(S)
          S1 <- crearVector(p - 1)
          S2 <- crearVector(longitud(S) - p)
          S1 <- S[1... p - 1]
          S2 <- S[p + 1... longitud(S)]
          S1 <- QuickSort(S1)
          S2 <- QuickSort(S2)
          S  <- S1 + S[p] + S2
     fin si
     devolver S
fin QUICKSORT

El pseudocódigo para el método pivot es el siguiente

PIVOT
Entrada: S -> secuencia de enteros.
Salida:  p -> posición del elemento utilizado para pivotear.

     p <- S[1]
     k <- 2
     t <- longitud(S)
     mientras S[k] <= p y k < longitud(S)
          k <- k + 1
     fin mientras
     mientras S[t] > p
          t <- t - 1
     fin mientras
     mientras k < t
          aux <- S[k]
          S[k] <- S[t]
          S[t] <- aux
          mientras S[k] <= p
               k <- k + 1
          fin mientras
          mientras S[t] > p
               t <- t - 1
          fin mientras
     fin mientras
     aux <- S[1]
     S[1] <- S[t]
     S[t] <- aux
     devolver t
fin PIVOT

Análisis de Complejidad Temporal

Analizando el método pivot en primera instancia podemos ver que su costo es de O(n) ya que los "mientras" anidados tienen como restricción el "mientras" principal. A su vez, el método QuickSort posee dos llamadas recursivas.

Dependiendo la ubicación del pivot (ya habíamos visto que cuanto más cerca del elemento mediano mayor eficiencia tendría el método), si el mismo cae cerca del centro de la cadena, el análisis de costos es el siguiente:

 

 

Se tiene que a = 2, b = 2 y k = 1 lo que finalmente da lugar a un costo O(n*log(n)) al igual que el método MergeSort.

Por el contrario, si el pivot cae cerca de alguno de los extremos (el peor caso), tenemos

 

 

 

Aquí a = 1, b = 1 y k = 1 (estamos en el Caso 1 de los métodos recursivos) dando una complejidad de O(n²).

En el peor de los casos, este algoritmo es menos eficiente que MergeSort. Cabe mencionar que en situaciones de la vida cotidiana, donde los datos tienen una distribución aleatoria (cualquiera de los ordenamientos es igualmente probable), se puede demostrar (está fuera de los alcances de este curso) que si bien el orden es igual para ambos algoritmos en el caso promedio, el tiempo de ejecución es menor para QuickSort.

 

 

 

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 13. Métodos de ordenamiento: QuickSort (Parte I)

QuickSort

Pondremos nuestra atención en el funcionamiento de un nuevo método de ordenamiento que también utiliza la técnica de DyC, el QuickSort.

La idea principal del mismo consiste en elegir un elemento al azar, denominado pivot y, a partir de ese elemento, dividir la cadena en dos partes:

• A la izquierda del pivot todos los elementos menores
• A la derecha del pivot todos los elementos mayores.

Al hacer esto, el pivot queda ubicado en su posición definitiva dentro de la cadena, es decir, queda ordenado. Luego se aplica en forma recursiva el método a las dos partes restantes.

Existen distintas técnicas para la elección del pivot. Cabe destacar que una buena selección del elemento pivot significará una solución más eficiente. Cuanto más cercano al elemento mediano se encuentre el pivot, más parejas serán las dos partes de la cadena y mejor la solución. Por el contrario, cuanto más cercano a alguno de los extremos se encuentre el pivot, las partes serán más desparejas y la solución menos eficiente.

Al igual que con MergeSort veremos un ejemplo ilustrado que nos ayude a comprender la forma en que trabaja el método. Supondremos a continuación que nuestro algoritmo siempre selecciona como pivot el primer elemento de la cadena.

Señalamos a continuación el elemento pivot en negrita en las sucesivas llamadas recursivas.

Se puede observar que, a medida que el pivot es elegido, va quedando en la posición que le corresponde en la cadena ordenada. Verificar por ejemplo que el primer pivot, el número "15", queda sexto cuando es elegido y en la última cadena (la ordenada) también ocupa esa posición.

 

En el próximo capítulo presentaremos el pseudocódigo para el método de QuickSort así como también el análisis de complejidad temporal.

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán. 

Capítulo 12. Métodos de ordenamiento: MergeSort (Parte II)

En el capítulo anterior nos enfocamos en entender cómo funciona el método de ordenamiento denominado MergeSort. En esta oportunidad presentaremos el pseudocódigo y realizaremos el análisis de complejidad temporal para mostrar que esta técnica mejora las estudiadas previamente.

 

Pseudocódigo

 

 

Para mayor claridad se utiliza el método "Merge" que se encarga de combinar las subcadenas

 

 

 

Análisis de Complejidad Temporal

 

Podemos observar que en el algoritmo MergeSort se realizan 2 llamadas recursivas y la entrada va reduciéndose a la mitad en cada instancia. Por lo tanto nos encuadramos en el Caso 2 con un valor de a = 2.

 

Las operaciones no afectadas por la recursividad tienen una complejidad lineal, es decir, orden O(n) dando un valor de 1 para k. Como dijimos, al reducir la entrada por la mitad, el valor de b es 2.

 

Resumiendo, tenemos que a = b^k (ya que 2 = 2¹)  y entonces el costo del algoritmo es O(n*log n).

 

Esto representa una mejora a los algoritmos de inserción y selección que tenían una complejidad cuadrática. En el próximo capítulo veremos el método de ordenamiento QuickSort, también basado en la técnica de DyC.

 

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 11. Métodos de ordenamiento: MergeSort (Parte I)

MergeSort

 

En este capítulo estudiaremos el método de ordenamiento conocido como MergeSort. Es un ejemplo de aplicación de la técnica de Divide y Conquista y, como veremos, el costo de su algoritmo es menor al de los métodos de selección e inserción vistos previamente.

 

La técnica consiste en dividir la cadena de entrada en dos mitades, ordenar cada una de las mitades y luego mezclar las mitades ordenadas en una nueva cadena ordenada.

 

Centraremos nuestra atención en un ejemplo simple que ayude a comprender el funcionamiento del algoritmo.

 

Se dispone de la siguiente cadena de enteros desordenada:

 

 

Lo que hacemos ahora es ir dividiéndola en mitades cada vez más pequeñas

 

 

En el algoritmo se verá que en cada iteración creamos 2 cadenas (una para la primera mitad y otra para la segunda mitad) y luego realizamos una llamada recursiva para cada una de ellas.

 

 

El caso base del algoritmo recursivo se producirá cuando la cadena de entrada tenga longitud igual a 1.

 

 

Una vez alcanzado el caso base, empezamos a combinar ordenadamente las subcadenas

 

 

 

Para obtener finalmente la cadena ordenada

 

 

 

 

En la próxima entrega veremos el pseudocódigo y analizaremos la complejidad temporal de MergeSort.