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 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 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 10. Métodos de ordenamiento: Inserción

El algoritmo para el método de ordenamiento por inserción consiste en ir ubicando cada elemento en su posición. Esto quiere decir que en cada iteración i se obtiene una secuencia ordenada de i - 1 elementos en la primera parte del arreglo y se inserta el elemento de la posición i para que ahora la secuencia de i elementos quede ordenada.

 

El pseudocódigo del algoritmo es el que sigue:

 

 

 

Al igual que en caso del ordenamiento por selección, las operaciones de asignación y comparación están incluidas dentro de dos bloques "para" lo que finalmente se traduce en una complejidad temporal de O(n²)

Fuentes:

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

Capítulo 9. Métodos de ordenamiento: Selección

Antes de  estudiar los métodos de ordenamiento que utilizan la técnica de Divide y Conquista, centraremos nuestra atención en los métodos de selección e inserción.

 

El objetivo es analizar la complejidad temporal de estos métodos más clásicos a fin de justificar la utilización de técnicas más eficientes.

 

El método de ordenamiento por selección consiste en ir buscando el menor de los elementos, colocarlo en la primera posición de una cadena, luego buscar el menor de los restantes, colocarlo en la segunda posición y así sucesivamente hasta que la cadena quede ordenada.

 

Presentamos el pseudocódigo de este método:

 

 

 

Sin hacer un análisis muy detallado podemos observar que las operaciones de asignación y comparación están embebidas en dos bloques "para", lo cual ocasiona que la complejidad temporal del método de selección sea O(n²)

 

Fuentes:

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

Capítulo 8. Divide y Conquista (Parte IV)

En este capítulo veremos un nuevo ejemplo de aplicación de la técnica de DyC.

 

Problema

Sea A[1...n], n >= 1, un vector de enteros diferentes y ordenados crecientemente, tal que algunos de los valores pueden ser negativos. Diseñar un algoritmo que devuelva un índice natural k, 1 <= k <= n, tal que A[k] = k, siempre que tal índice exista.

Pseudocódigo



 

La letra C significa que ese bloque tiene una complejidad temporal constante.

 

Análisis de complejidad Temporal

Vemos que el tamaño de la entrada se reduce a la mitad, por lo tanto nos encuadramos en el Caso 2

 

a = 1

b = 2

k = 0

 

Notar que 'a' es igual a 1 porque nunca se ejecutan ambos bloques (si uno se ejecuta, el otro no)

 

Reemplazando estos valores de los parámetros el costo del método queda en O(log n)

 

En este ejemplo, pusimos como pre condición, que el vector de enteros estuviera ordenado en forma creciente. En los próximos capítulos veremos métodos de ordenamiento que utilizan la técnica de Divide y Conquista para ordenar una cadena.



Capítulo 3. Ejemplos de Análisis de Complejidad Temporal en Métodos Recursivos

Veremos algunos ejemplos de aplicación para lo aprendido en el Capítulo anterior.

Comencemos por analizar la función factorial. Definiremos un algoritmo recurrente para la misma utilizando la notación de pseudocódigo.

Notemos que el caso base ocurre cuando la entrada 'n' es igual a 0 o a 1.

Luego se produce la llamada recursiva decrementando el tamaño de la entrada en una unidad. Esto nos indica que estamos en presencia del Caso 1.

Recordamos del Capítulo 2 que para este caso, el orden de la función venía dado por la relación entre 'a' (la cantidad de veces que se llama la función recursiva) y 1

Como se puede apreciar, aquí realizamos una única vez la llamada recursiva (pues la misma no se encuentra dentro de un bucle), siendo a = 1 entonces.

Nos resta determinar el valor de 'k', el grado del polinomio p(n)

A simple vista podemos ver que existe una única instrucción además de la llamada recursiva, y la misma tiene un valor constante (se devuelve un valor). Por lo tanto, el polinomio p(n) es una constante y finalmente k = 0.

Este análisis nos lleva a determinar el orden la función factorial recursiva en O(n)

A continuación analizaremos la complejidad temporal de ejemplos generales, sin entrar en detalles de qué propósito cumple el algoritmo.

Ejemplo 1

Se da como dato que el orden del método "calcularCondicion" es O(log n) y el orden del método "procesar" es O(n)

Este ejemplo se enmarca dentro del caso 2 ya que el tamaño de la entrada es dividido (en este ejemplo por 3). 

El análisis de complejidad temporal queda:

a = 1 ya que existe una única llamada recursiva. Que no nos confunda el hecho que veamos tengamos la llamada en dos bloques si distintos. Precisamente, por cada instancia de ejecución del método 1 se ejecutará, o bien las instrucciones dentro del bloque 'si', o bien las instrucciones dentro del bloque 'sino', pero nunca se ejecutarán ambas. Por ello a = 1.

Queda claro que b = 3, pues es la cantidad que divide a la entrada

Sólo resta determinar el valor de k. Por los datos proporcionados vemos que la función procesar tiene orden O(n) y la función  calcularCondicion O(log n). Siendo n mayor a log n consideraremos el peor de los casos, o sea, O(n). Esto hace que k = 1.

Resumiendo, debemos ver la relación entre a y b^k siendo a = 1, b = 3 y k = 1. 

Claramente a < b^k ya que 1 < 3. 

Finalmente tenemos que el orden del Método 1 es O(n^k) = O(n)

NOTA: si no existiera la función "procesar", la única función no afectada por la recursividad sería calcularCondicion con un orden O(log n). En dicho caso, debe hacerse el análisis para k = 0 y también k = 1, quedándonos con el que arroje el peor resultado.

Ejemplo 2

Se da como dato que el orden los métodos "calcularCondicion" y "procesar" es O(c), es decir, constantes.

A diferencia del método anterior, aquí podemos ver que existen 2 llamadas recursivas en un único bloque, por lo tanto a = 2.

La entrada se divide en dos, resultando b = 2 y como "calcularCondicion" y "procesar" son ambos métodos constantes, k = 0

Como la entrada es dividida estamos en presencia del caso 2

La relación es a > b^k  siendo el orden O(n^log_b^a), reemplazando los valores nos queda O(n)

Ejemplo 3

Se da como dato que el orden del método "calcularValor" es constante y el orden del método "procesar" es O(n*log n)

Este ejemplo se encuadra en el caso 1 ya que se sustraen elementos de la entrada. Tenemos dos llamadas recursivas, por ende, a = 2. La entrada disminuye en un elemento, por ello, b = 1.

Para el valor de k, el método procesar tiene un O(n*log n) pero notemos que está incluido dentro de un bloque mientras (comunmente llamado while). Entonces debemos multiplicar este orden por la cantidad de veces que se ejecute el bloque. En el peor de los casos, el bloque se ejecutará n veces (ya que ingresa mientras val < n). Por lo tanto el costo del bloque será n * n*log n.

Aquí debemos entonces analizar qué pasa en los casos que k = 2 y k = 3 y quedarnos con el peor.

Vemos que a = 2 es mayor a 1, por ello estamos en presencia de un costo del orden O (a^{n div b}), 

resultando en una complejidad exponencial O(2ⁿ)

Capítulo 2. Complejidad Temporal de Métodos Recursivos

Algoritmos Recursivos

Un algoritmo recursivo es aquel que expresa la solución a un problema en términos de una llamada a sí mismo. Esta llamada a si mismo se denomina llamada recursiva o recurrente. Para evitar un ciclo sin fin es muy importante definir lo que se conoce como el caso base o condición de corte.

A lo largo del curso se utiliza la notación de pseudocódigo de forma tal que cada uno pueda utilizar el lenguaje de programación que le resulte más familiar para implementar el algoritmo.

A continuación presentamos un ejemplo general de un método recurrente.

Este algoritmo genérico sirve para ilustrar a que nos referimos cuando decimos caso base.

Llamamos 'proceso' a una función que se encargue de realizar algo con la entrada, ya sea sumarle una constante o ejecutar cualquier cosa que sea de interés para nuestro problema.

En el caso que la entrada al método A no cumpla la condición de base, se efectúa la llamada recurrente, restando una constante 'c' a la entrada.

Es lógico que se reduzca la entrada en alguna forma, sino no podríamos llegar nunca al caso base y de esa manera finalizar la ejecución del algoritmo.

Consideraremos dos formas de reducir la entrada: restando o dividiendo. Con cualquiera de ellas estamos logrando el objetivo. Sin embargo, veremos que el análisis de complejidad temporal varía dependiendo del caso.

Antes de profundizar en cada caso, notar las siguientes definiciones para comprender la notación:

Caso 1: Sustracción sobre la entrada

Este es el caso visto en el ejemplo del método A. La función que representa el costo para estos casos es

Para este caso de sustracción, lo que determina el costo del algoritmo será el valor de 'a' respecto de 1 como se ve a continuación:

Caso 2: División de la entrada

En este caso, en lugar de restar algún elemento de la entrada, lo que hacemos es dividir la misma generando así entradas más pequeñas para la llamada recursiva. La función que representa el costo para este caso es

El costo del algoritmo en estos casos estará determinado por la relación existente entre los parámetros a, b y k (grado del polinomio f(n))

En el próximo capítulo utilizaremos estas funciones para analizar la complejidad temporal de algunos ejemplos de métodos recurrentes.

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

Capítulo 1. Algoritmos y Complejidad Temporal

¿Qué es un algoritmo?

Básicamente, un algoritmo es un conjunto finito de instrucciones ordenadas. Transforman datos de entrada en datos de salida resolviendo algún problema en particular.

Con salida correcta queremos decir que, ante una determinada entrada válida, se genere un resultado esperado.

Es independiente del lenguaje de programación. Cuando lo trasladamos a un lenguaje en particular, estamos generando un programa.

Vamos a considerar dos tipos distintos de complejidad para el análisis de algoritmos:

• Temporal: Medida de eficiencia o de tiempo.
• Espacial: Cuánto me ocupa la resolución del algoritmo.

No nos ocuparemos en el curso de la complejidad espacial, pero es importante tenerla en cuenta cuando se dispone de recursos limitados.

Complejidad Temporal

Podemos organizar la Complejidad Temporal en dos categorías:

• Teórica: Podemos hacer un análisis previo a la ejecución.
• Real: Tenemos dependencia del hardware, recursos, etc.

Centraremos nuestra atención sobre la Complejidad Temporal Teórica. De aquí en adelante nos referiremos a ella simplemente como complejidad temporal.

Para realizar el análisis del costo de un algoritmo debemos tener en cuenta:

• La cantidad de datos de entrada (tamaño de la entrada).
• Análisis de las operaciones elementales (suma, asignación, comparación, etc).
• Análisis de casos (mejor, promedio, peor).

En general, el costo de un algoritmo dependerá del tamaño de la entrada y por ello resulta conveniente definirlo como una función de n donde n representará el tamaño de la entrada.

Utilizaremos O(n) para expresar la función del costo de un algoritmo:

Dependiendo del tamaño de la entrada tendremos los siguientes costos (ordenados de menor a mayor costo):

• O(c) - Constante. Es independiente de los datos de entrada. En general las operaciones elementales tienen un costo constante (suma, asignación, comparación).
• O(log n) - Logarítmica. 
• O(n) - Lineal. La cantidad de operaciones crece linealmente con la cantidad de elementos de entrada.
• O(n*log n)
• O(n²) ... O(n^x) - Polinomiales.

También están aquellas que no son aplicables para un algoritmo:

• O(xⁿ)
• O(n!)

En el próximo capítulo aplicaremos estos conceptos a métodos recursivos.

Fuentes: 

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