PDF de programación - Diseño y Análisis de Algoritmos - Tarea 1

Universidad Diego Portales

Escuela de Informática y

Telecomunicaciones

Diseño y Análisis de Algoritmos

Tarea 1

Alumnos:
Josefa González Mejías
Guillermo Iglesias
Birkner

Profesor:
Diego Caro
Ayudante:
Farid Abulias

Abril 15, 2016

2

2
3
3
4
4

5
5
5
6

7
7
8

8

9

Índice

1. Introducción

2. K-ésimo elemento

2.1.1. Análisis

2.1. Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Mediana de Medianas . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1. Análisis

3. Top-M

3.1. Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1. Análisis

4. Experimentación

4.1. K-ésimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Top-M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Conclusión

6. Referencias

1

1.

Introducción

A continuación se diseñará, analizarán y compararán distintos algoritmos
de selección que permitan resolver el problema de encontrar el k-ésimo y
top-M elementos más pequeño que se encuentra en un arreglo.

Los algoritmos de selección que permiten encontrar el k-ésimo elemento
más pequeño dentro de un arreglo o vector, deben de encontrar en primer
lugar la mediana de un conjunto de números, la cual es un caso particular
dentro de un algoritmo de selección, esto se debe a que el algoritmo no pue-
de garantizar que haya encontrado el k-ésimo termino sin haber analizado e
identificado los otros k - 1 elementos que son menores que el valor buscados,
ni el resto de elementos pertenecientes al N - k valores mayores. Los algorit-
mos de selección de este tipo tienen muchas aplicaciones en los procesos de
datos experimentales y de otros tipos, como por ejemplo el uso de la mediana
y de otras estadísticas de orden para dividir archivos en otros más pequeños
sin una gran cantidad de cálculos extras.

Existen otros algoritmos de selección para encontrar los top-M elementos
menores de un arreglo, el cual retorna los M valores más pequeños dentro
de un arreglo. Esta clase de algoritmos de enfocan en comparar la frecuencia
de un grupo de datos, en cuanto a usuarios, como por ejemplo el top de las
películas más vistas, libros, canciones y otros tipos de productos, mientras
en el enfoque de mercado este tipo de algoritmo se utiliza para analizar la
información, como la diferencia o similitudes entre elementos (productos), con
la finalidad de utilizar luego esta información para recomendar de forma más
rápida el elemento, como por ejemplo para una empresa que necesite saber
cuales son productos más solicitados por lo usuarios, este tipo de algoritmo le
entregara un resultado de tamaño M con todos los productos más vendidos.

2. K-ésimo elemento

Para resolver el problema del k-ésimo termino menor se implementará el
algoritmo de selección Merge Sort como solución sencilla, el cual posee un
orden de complejidad de O(nlogn) para cualquier tipo de situación, es decir,
que se cumple esa orden de complejidad para el caso promedio, mejor y peor.
Además como solución mejorada para resolver el problema de encontrar
el k-ésimo elemento se utilizara el algoritmo Mediana de Medianas, el cual
posee un orden de complejidad para su peor caso de O(n).

2

2.1. Merge Sort

Algoritmo de ordenamiento externo que combina múltiples entradas orde-
nadas en una única salida, es decir, que particiona en sublistas cada vez más
pequeñas el arreglo con el fin de combinar las soluciones pequeñas, uniendo
las sublistas ya ordenadas en una sola lista.

Este tipo de ordenamiento esta basado en la utilización de divide and
conquer ya que divide la lista a la mitad en cada recursión hasta que su
longitud sea de 0 ó 1, se ordenas estas pequeñas sublistas y se mezclan para
obtener una sola ordenada, esto se debe a que se necesita menos pasos para
ordenar una lista grande ya que solo se deben entrelazar las listas pequeñas
ordenadas.

2.1.1. Análisis

A través del algoritmo utilizado en el experimento, es posible desarrollar
la ecuación de recurrencia siguiendo los diferentes pasos de este. Dado un
arreglo de n elementos, cada llamada recursiva entrega un arreglo de largo
n/2 hasta que el largo de cada uno de esos subarreglos sea de 1. Para definir
esta ecuación de recurrencia, es necesario analizar los diferentes componentes
de la estrategia divide and conquer.

Dividir : Dividir el problema, en subarreglos de largo n/2 para cada uno,

toma un tiempo constante. O(1)

Conquistar : Recursivamente se resuelven los dos subproblemas generados,
cada uno de largo n/2, lo cual entrega un tiempo de ejecución de 2T (n/2).
Combinar : Para este experimento se utilizó la librería heapq, del lenguaje
Python la cual posee la función heapq.merge() que se encarga de mezclar los
subarreglos en una nueva lista, lo cual ocurren en un tiempo O(n)

Teniendo en cuenta los factores mencionados, es posible determinar la

función de recurrencia de MergeSort de la siguiente manera:
si, n = 1
si, n > 1

T (n) =

+ O(n)

Utilizando el caso 2 del teorema maestro, dice:
- Si f (n) = θ(nlogba) entonces, T (n) = θ(nlogbalogn)
- Como se tiene: a = 2, b = 2 y f (n) = O(n).
- Finalmente f (n) = θ(nlog22) = O(n)
- Por lo tanto se comprueba que T (n) = O(nlogn)

O(n)
2T n

2

3

2.2. Mediana de Medianas

Mediana de medianas es un algoritmo de selección basado en Quick Select,
el cual encuentra la mediana aproximada de un arreglo, en tiempo lineal, el
cual será utilizada como pivote para luego encontrar el k-ésimo termino.

Este algoritmo inicia con la división del arreglo en sublistas de longitud
de cinco, los cuales se clasificarán independientemente para determinar la
mediana de cada una, se llama de forma recursiva para obtener la mediana
de las medianas y utilizar éste como pivote.

Luego, a partir del pivote (i) seleccionado, se dividirá la lista en dos
sublistas, una que contenga los elementos más pequeños que el pivote y el
otro que contenga los elementos mayores a él. Utilizando el índice del pivote
se tiene que:

- Si k = i entonces el pivote es el k-ésimo elemento y retorna.
- Si k > i el elemento es mayor que el pivote y se buscará en la lista con

los valores más grande.

- Si k < i entonces el elemento se menor que el pivote y se buscará en
la lista donde se encuentran los elementos menores,donde se encuentra el
(k − i − 1) elemento.

2.2.1. Análisis

La llamada recursiva del cálculo de la mediana no excede el comporta-
miento lineal del peor de los casos, esto debido a que la lista de medianas es
del 20 % del tamaño de la lista, mientras que la otra llamada recursiva llama
a lo más el 70 % de la lista.

Es posible desarrollar la recurrencia para el peor caso en tiempo T (n)
del algoritmo de Selección. Dividir los elementos en n
5 grupos de 5 elementos
cada arreglo, encontrar la mediana de cada grupo y particionar el arreglo
a partir de la mediana de medianas obtenidas, toma un tiempo de O(n).
Seleccionando recursivamente para encontrar la medianas x de las n
5 medianas

mencionadas anteriormente toma un tiempo de T 7n

10 + 6, asumiendo que

T esta incrementando monótonamente.

Se realiza la suposición, que cualquier input menor que 140 elementos
requiere un tiempo de O(1), a partir de lo cual se puede obtener la recurrencia:

T (n) ≤

si, n < 140
si, n ≥ 140

O(n)
T n

5

+ T 7n

10 + 6 + n

4

Se muestra que el tiempo de ejecución es lineal por sustitución. Asumien-
do que T (n) ≤ cn, siendo c una constante y para todo n < 140. También
se toma una constante a que describe la función del termino O(n) mostra-
do anteriormente (el cual describe el componente no-recursivo del tiempo
de ejecución del algoritmo) está acotado superiormente por an para todo
n > 0. Substituyendo entonces la hipótesis inductiva en el lado derecho de la
recurrencia, se obtiene:

5

10 + 6 + an
10 + an

10 + 6c + an

+ c 7n
T (n) ≤ c n
T (n) = cn +7c − cn

5 + c + 7cn
10 + 7c + an

T (n) ≤ cn
T (n) = 9cn

T (n) = O(n)

Por lo tanto, el tiempo en el peor de los casos de ejecución es lineal.

3. Top-M

Algoritmo de selección que busca en una lista de elementos los M mayores
o menores valores de este. Para resolver este tipo de problemas, de encontrar
el top en una lista se utilizara como solución sencilla el algoritmo Merge Sort
el cual posee un orden de complejidad de O(nlogn) para todos sus casos y
como solución mejorada se implemento,para este problema el algoritmo Heap
Sort el cual posee un orden de complejidad de O(n).

3.1. Merge Sort

El análisis es idéntico al mostrado anteriormente, para encontrar los Top-
M menores números, se ordena el arreglo utilizando M ergeSort en O(nlogn)
y posteriormente se retornar todos los elementos hasta la posición M en
tiempo constante O(1). Luego el algoritmo completo se ejecuta en O(nlogn)

3.2. Heap Sort

Algoritmo de ordenamiento no recursivo que utiliza una cola de prioridad,
es decir, ordena un vector de n elementos con los valores menores en las
primeras posiciones del arreglo en el caso que se este utilizando un min-heap,
mientras que en el caso contrario si se ordenas con los valores mayores del

5

vector este es un max-heap. Para resolver este problema, de encontrar el
Top-M se utilizo un min-heap.

3.2.1. Análisis

Dada la idea principal de querer construir un heap a partir de un arreglo,
que el costo de ingresar cada elemento en O(logn) dentro del árbol, es que
se encuentra una mejor solución, esta es la función heapify de la librería
heapq. Siguiendo la misma, idea, heapify busca ingresar cada elemento al árbol
bajo la idea contraria a la construiccion de heap común(Bottom-Up), esta se
denomina