Sea N
la longitud de la lista. Observamos lo siguiente:
- Para intercalar dos listas de longitud
N/2
hace falta recorrer ambas listas que en total tienenN
elementos, por lo que es proporcional aN
. Llamemosa * N
a ese tiempo. - Si llamamos
T(N)
al tiempo que tarda el algoritmo en ordenar una lista de longitudN
, vemos queT(N) = 2 * T(N/2) + a * N
. - Además, cuando la lista es pequeña, la operación es de tiempo
constante:
T(1) = T(0) = b
.
# Código 20.1: mergesort.py: Una implementación de *Merge sort
#!/usr/bin/env python
#encoding: latin1
def merge_sort(lista):
""" Ordena lista mediante el método merge sort.
Pre: lista debe contener elementos comparables.
Devuelve: una nueva lista ordenada. """
# Una lista de 1 o 0 elementos, ya está ordenada
if len(lista) < 2:
return lista
# Si tiene 2 o más elementos, se divide al medio y ordena cada parte
medio = len(lista) / 2
izq = merge_sort(lista[:medio])
der = merge_sort(lista[medio:])
return merge(izq, der)
def merge(lista1, lista2):
""" Intercala los elementos de lista1 y lista2 de forma ordenada.
Pre: lista1 y lista2 deben estar ordenadas.
Devuelve: una lista con los elementos de lista1 y lista2. """
i, j = 0, 0
resultado = []
# Intercalar ordenadamente
while(i < len(lista1) and j < len(lista2)):
if (lista1[i] < lista2[j]):
resultado.append(lista1[i])
i += 1
else:
resultado.append(lista2[j])
j += 1
# Agregar lo que falta, si i o j ya son len(lista) no agrega nada.
resultado += lista1[i:]
resultado += lista2[j:]
return resultado
Para simplificar la cuenta vamos a suponer que N = 2^k
.
T(N) = T(2^k) = 2 * T(2^k−1) + a * 2^k (20.1) = 2 * (2 * T(2^k−2) + a * 2^k-1) + a * 2^k (20.2) = 2^2 * T(2^k−2) + a * 2^k + a * 2^k (20.3) ... (20.4) = 2^i * T(2^k−i) + i * a * 2^k (20.5) ... (20.6) = 2^k * T(1) + k * a * 2^k (20.7) = b * 2^k + k * a * 2^k (20.8)
Pero si N = 2^k
entonces k = log2 N
, y por lo tanto hemos
demostrado que:
T(N) = b x N + a x N x log2 N (20.9)
Como lo que nos interesa es aproximar el valor, diremos (despreciando
el término de menor orden) que T(N) = N * log2 N
. Hemos
mostrado entonces un algoritmo que se porta mucho mejor que los que
vimos en la unidad pasada.
Si analizamos el espacio que consume, vemos que a cada paso genera una nueva lista, de la suma de los tamaños de las dos listas, es decir que duplica el espacio consumido.
Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola,
Maximiliano Curia, Marcos Medrano, Nicolás Paez.
La copia y redistribución de esta página se permite bajo los términos
de la licencia Creative Commons Atribución - Compartir Obras Derivadas
Igual 3.0 siempre que se conserve esta nota de copyright.