Complejidad De Colorear Mapas

Para la implementación del ejercicio 1 para el método “public void colorear()” se nos hizo conveniente utilizar un método auxiliar para facilitarnos recorrer los colores limítrofes. El método “public ArrayList<Integer> colorearAux(Zona n)” toma como parámetro una Zona, y devuelve una ArrayList con los colores utilizados por los países limítrofes de respectiva zona, luego de tener esa lista lo único que queda es constatar no repetir los colores ya pintados, y pintando siempre desde el primer color en adelante para poder utilizar la menor cantidad posible de estos.

Para el método “public int cantColores()” siguiendo con la misma línea del método anterior creamos un ArrayList con los colores de la zonas (sin repetir) y luego se devuelve su largo.

El método “ public boolean verificarColoreo()” que verifica el mapa este bien coloreado,es decir, que dos zonas limítrofes no tengan el mismo color.

c) Calcular el orden de complejidad asintótica para el peor caso de los tres métodos.

El método auxiliar de colorear()

Nombres de las variables que determinan el tamaño del problema:

 n= n.getLimitrofes().size() = iesimoLimitrofes(i)

Ya que el iesimoLimitrofe y el largo de la lista de limítrofes del mismo país son en función del largo de la misma lista tendrá el mismo valor N1

 ñ= el largo de Zona.(colorZona recorre todas las zonas en el peor caso)

Complejidad= 2+ ((2n+2)*(1ñn))+1 =3(2n*1n*ñ+2*n*ñ) =3(2n^2*ñ+2nñ)= 6n^2*3ñ+6n*3ñ

Como 6n^2*3ñ>6n*3ñ me quedo con el termino más grande= 6n^2

La complejidad en O(n^2)

El método colorear()

Nombres de las variables que determinan el tamaño del problema:

 ñ= zonas.size();

 m= el largo de la lista que devuelve colorearAux() (contiene la complejidad de n^2 de llamar al método.)

Como en el peor de los casos es que entre al primer if y evalué mayor cantidad de limítrofes, vamos a evaluar solo ese caso.

Complejidad= (2ñ+2)*(2m+2)*(2+2m)= (2ñ+2)*(4m^2+8m+4)= 4m^2*2ñ+8m*2ñ+8ñ

Me quedo con el termino más grande= 4m^2*2ñ

La complejidad es O(m^2*ñ)

El método verificarColoreo()

 n=zonas.size().

...