Este post continua con una pequeña observación sobre lo visto en el post Problema de Algoritmia Básico, Análisis de Complejidad.

Voy a continuar en este post trabajando sobre la solución básica, analizando el comportamiento de la función esta_en_lista() ante diferentes inputs.

Listas ordenadas con un alfabeto finito

Supongamos que el alfabeto que tienen las listas posibles tiene un tamaño finito, o lo que es lo mismo que el numero de ints posibles es finito, y ademas que las listas son ordenadas y de mayor tamaño al tamaño del alfabeto.

Por ejemplo, tomemos un alfabeto de tamaño 3:

[1,2,3,1,2,3,1,2,3,….]

Sabemos por el análisis del post referido que mientras se va construyendo la lista pasados, se necesita iterar por cada elemento menor hasta incluirlo en la lista. Sabemos así mismo que una vez construida la lista pasados por cada elemento repetido se necesita pasar por todos lo elementos anteriores antes de encontrar al elemento. Por esto, sabemos que el costo asociado a cada elemento es:

T(n%3 == 0) = 2a + w
T(n%3 == 1) = 1a + w
T(n%3 == 2) = 0a + w

Donde a es el costo de iterar por cada elemento de la lista y w es una constante que representa el resto de las operaciones (constantes) de la función, n es la posición del elemento en la lista y Usamos la notación n%3 == x para representar aquellos valores de n en el que el modulo 3 es igual a x

Para el resto del post vamos a olvidarnos de w y preocuparnos solamente por a ya que es aqui donde se producen las operaciones que son variables de la función (por el costo de iterar por la lista).

Es evidente que en una sucesión de listas ordenadas de tamaño 3, la cantidad de veces que se cumplirá la llamada a cada uno de los valores de la recurrencia es 1/3 * n. O sea, en el total de la lista se cumple que 1/3 de los valores son 1, un tercio son 2 y un tercio son 3.

Nos queda entonces el costo total de las llamadas a la función por iterar por cada uno de los elementos como:

Total = 1/3 * n * T(n%3==0) + 1/3 * n * T(n%3 == 1) + 1/3 * n * T(n%3 == 2)

Esta formula puede ampliarse para cualquier tamaño de alfabeto:

Total = 1/k * n * T(n%k == 0) + 1/k * n * T(n%k == k-1) + 1/k * n * T(n%k == k-2) + … + 1/k * n * T(n%k == 1)

Donde k es el tamaño de alfabeto. Ademas sabemos (de acuerdo al análisis del post anterior) que:

T(n%k == 0) = (k-1)a
T(n%k == 1) = (k-2)a
T(n%k == 2) = (k-3)a
...
T(n%k == k-2) = 1a
T(n%k == k-1) = 0a

Por lo que esta formula puede plantearse entonces como:

Total = 1/k * n * (k-1)a + 1/k * n * (k-2)a + 1/k * n * (k-3)a + … + 1/k * n * 1a

O lo que es lo mismo:






i
=
1

k



1
k

n

(
i

1
)

a

Repensando el peor caso

En el peor caso se cumple que la lista esta ordenada y el tamaño del alfabeto es igual al tamaño de la lista, por consiguiente la formula:






i
=
1

k



1
k

n

(
i

1
)

a

Se reduce a:






i
=
1

n



1
n

n

(
i

1
)

a

=






i
=
1

n



(
i

1
)

a

=





(
n

1
)

n

2


Que es la equivalencia que vimos anteriormente.

Que pasa si no es una lista ordenada?

Supongamos que la lista no es ordenada y supongamos un alfabeto de tamaño k. En este caso hasta que no se sucedan los k valores del alfabeto, el costo asociado a cada entero no se corresponde directamente con la tabla planteada anteriormente. Por ejemplo si se presenta un 3 como primer elemento, no se van a cumplir 2 iteraciones sino 0, ya que la lista pasados esta vacia. Esto sucederia hasta que aparezcan en la lista todos los elementos del alfabeto.

Podemos plantear (ingenuamente) para este caso una funcion de aproximacion que seria la siguiente:

Total = 1/k * n * (k-1)a + 1/k * n * (k-2)a + 1/k * n * (k-3)a + … + 1/k * n * 1a – j

Donde j representara la disminucion producida en relacion a la formula anterior hasta que se suceden todos los valores de la lista.

Es evidente que, manteniendo fijo el tamaño de alfabeto, y con un tamaño de lista lo significativamente mayor al tamaño de alfabeto, j se vuelve en el caso tipico despreciable en el costo total de la funcion.

Sin embargo analizar el caso promedio sigue siendo muy complicado. Hica varios intentos y me quedaba una formula enorme, por consiguiente decidi hacer una simulacion matematica para evaluarlo y es el tema del ultimo y final post de esta serie.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Introduction to Algorithms, 2nd Edition; Cormen, Leierson, Rivest, Stein; MIT Press; 2009