Análisis de la complejidad de un algoritmo

Siguiendo con nuestro curso de programación y una vez explicadas las complejidades típicas de un algoritmo y su forma de calcularlas a partir de unos datos concretos ahora nos toca obtener esos datos. Esos datos serán los que utilicemos para representar las curvas que se asocien con cada complejidad, tendremos un eje de coordenadas donde el eje horizontal se corresponderá con el tiempo que tarde en ejecutarse para un tamaño n que estará representado en el eje vertical.

Algoritmo para medir tiempos

Lo primero que tendremos que hacer será diseñar un algoritmo que nos permita medir los tiempos para los n tamaños del problema. Haremos uso de un método que nos vaya generando para cada problema varias mediciones y luego nos haga la media aritmética.

public void test(String output, int times, int startN, int endN,        String nombreClase, String nombreMetodo) {    FileWriter file = null;    PrintWriter pw;    try {        file = new FileWriter(output);        pw = new PrintWriter(file);        Algorithms alg = new Algorithms();        for (int n = startN; n <= endN; n++) {            long local = 0;            for (int j = 0; j < times; j++)                local += testAlgorithm(nombreClase, nombreMetodo, n);            long total = local / times;            pw.println(n + ", " + (total));        }    } catch (Exception e) {        e.printStackTrace();    } finally {        if (file != null)            try {                file.close();            } catch (IOException e) {                e.printStackTrace();            }    }}

En este método básicamente lo que hacemos ir midiendo los tiempos de un tamaño recibido hasta un tamaño final y luego guardarlo todo en un fichero. Este método nos sirve para medir cualquier método que reciba por parámetro un entero y devuelva un entero para ello hacemos uso de un método auxiliar.

public long testAlgorithm(String className, String methodName, int n) {    long tInicial = 0, tFinal = 0;    Class<?> cl;    try {        cl = Class.forName(className);        Object o = cl.newInstance();        Method m = cl.getMethod(methodName, int.class);        tInicial = System.currentTimeMillis();        m.invoke(o, n);        tFinal = System.currentTimeMillis();    } catch (Exception e) {        e.printStackTrace();    }    return tFinal - tInicial;}

Es un poco lioso, pero con quedarse que esta es una de las formas que tiene Java 7 (en 8 se podría pasar por parámetro una función/método) y otros lenguajes de comprobación estática de pasar una función por parámetro. Esta técnica se llama reflexión computacional que lo que hace es permitirnos cambiar el método al que llamemos según sea el valor del String pasado. Este es un parche que incorporan este tipo de lenguajes sin soporte al paradigma funcional, y que por tanto por ahora esto no nos interesa.

Vamos a poner estos dos métodos en una clase que denominemos TestBench.

Usando el algoritmo

Es habitual usar este tipo de código no en el propio programa, si no en una clase especial denominadas JUnit. Por ahora no entraremos en mucho detalle de lo que son, únicamente comentar que tipo de clases se utilizan para verificar que un programa funciona perfectamente. Habitualmente son llamadas como nombre de clase que prueban + test. Si por ejemplo queremos una clase para medir la clase pow2 se llamará pow2test.

El termino JUnit es el usado para llamar a las pruebas unitarias del lenguaje Java, aunque es algo más, es un conjunto de clases creadas por Erich Gamma y Kent Beck para hacer pruebas unitarias de aplicaciones Java.

Vamos a crear una nueva JUnit, para ello en Eclipse vamos. Seguimos os siguientes pasos:

• Vamos a crear un nuevo proyecto, así explicaremos algunos conceptos que hemos omitido hasta ahora.

• Añadimos un nuevo package denominados pruebas, es importante que las pruebas y el código para el cliente estén separados, estén en diferentes package ya que es lo normal es que cuando proporcionemos al cliente el programa no incluyamos las pruebas.

• Creamos una nueva JUnit dentro de nuestro paquete pruebas llamada ComplejidadTest

• Por último añadimos nuestra clase TestBench, nuestra clase Algorithms y la clase Pow2 a un nuevo paquete que creemos denominado source.

Las clase Pow2 quedará modificada, se le debe quitar el main y añadirle el nombre del paquete al que pertenece.

package source;public class Pow2 {/** * Método que calcula las potencias de 2 de manera iterativa */public double pow2Iter(int n) {    double valor = 2;    if (n == 0)        return 1;    else        for (int i = 1; i < n; i++) {            valor += valor;        }    return valor;}/** * Método que calcula las potencias de 2 de manera recursiva */public double pow2Rec(int n) {    if (n == 0)        return 1;    else        return 2 * pow2Rec(--n);}public double pow2Rec2(int n) {    if (n == 0)        return 1;    else if (n == 1) {        return 2;    } else {        return pow2Rec2(--n) + pow2Rec2(n);    }}public double pow2Rec3(int n) {    if (n == 0)        return 1;    else if (n % 2 == 0)        return pow2Rec3(n / 2) * pow2Rec3(n / 2);    else        return 2 * pow2Rec3(n / 2) * pow2Rec3(n / 2);}double cache = 0;public double pow2Rec4(int n) {    if (n == 0)        return 1;    cache = pow2Rec4(n / 2);    if (n % 2 == 0)        return cache * cache;    else        return 2 * cache * cache;}}

Si nos fijamos delante de nuestro métodos tenemos:

    /** *  XXX */

Sirve para definir el JavaDoc de la aplicación. El JavaDoc es la parte de la aplicación donde se detalla la documentación, por ahora esto no nos interesa pero necesario que los métodos de una clase estén correctamente documentados. En artículos siguientes veremos como se debe documentar una clase.

Cuando tengamos todo esto vamos a nuestra clase ComplejidadTest y añadimos el siguiente código:

package pruebas;import static org.junit.Assert.assertEquals;import org.junit.Test;import source.Pow2;import source.TestBench;public class ComplejidadTest {@Testpublic void testPow2() {    Pow2 t = new Pow2();    for (int i = 0; i < 62; i++)        assertEquals(Math.pow(2, i), t.pow2Iter(i), 0.0001);    for (int i = 0; i < 62; i++)        assertEquals(Math.pow(2, i), t.pow2Rec(i), 0.0001);    for (int i = 0; i < 30; i++)        assertEquals(Math.pow(2, i), t.pow2Rec2(i), 0.0001);    for (int i = 0; i < 62; i++)        assertEquals(Math.pow(2, i), t.pow2Rec3(i), 0.0001);    for (int i = 0; i < 62; i++)        assertEquals(Math.pow(2, i), t.pow2Rec4(i), 0.0001);}@Testpublic void testGraficasComplejidades() {    TestBench t = new TestBench();    // linear    double i = System.currentTimeMillis();    t.test("linear.txt", 5, 1, 30, "source.Algorithms", "linear");    double j = System.currentTimeMillis();    System.out.println("Fin linear--Tiempo:" + (j-i));    // cuadratico    i = System.currentTimeMillis();    t.test("cuadratica.txt", 5, 1, 30, "source.Algorithms", "cuadratica");    j = System.currentTimeMillis();    System.out.println("Fin cuadratica--Tiempo:" + (j-i));    // cubico    i = System.currentTimeMillis();    t.test("cubica.txt", 5, 1, 30, "source.Algorithms", "cubica");    j = System.currentTimeMillis();    System.out.println("Fin cubica--Tiempo:" + (j-i));    // logaritmico    i = System.currentTimeMillis();    t.test("logaritmico.txt", 5, 1, 30, "source.Algorithms", "logaritmico");    j = System.currentTimeMillis();    System.out.println("Fin recursivo3--logaritmico:" + (j-i));}@Testpublic void testGraficasPow2() {    TestBench t = new TestBench();    // iterativo    double i = System.currentTimeMillis();    t.test("pow2iterative.txt", 5, 1, 50, "source.Pow2", "pow2Iter");    double j = System.currentTimeMillis();    System.out.println("Fin iterativo--Tiempo:" + (j-i));    // recursivo    i = System.currentTimeMillis();    t.test("pow2recursivo1.txt", 5, 1, 50, "source.Pow2", "pow2Rec");    j = System.currentTimeMillis();    System.out.println("Fin recursivo1--Tiempo:" + (j-i));    i = System.currentTimeMillis();    t.test("pow2recursivo2.txt", 5, 1, 10, "source.Pow2", "pow2Rec2");    j = System.currentTimeMillis();    System.out.println("Fin recursivo2--Tiempo:" + (j-i));    i = System.currentTimeMillis();    t.test("pow2recursivo3.txt", 5, 1, 50, "source.Pow2", "pow2Rec3");    j = System.currentTimeMillis();    System.out.println("Fin recursivo3--Tiempo:" + (j-i));    i = System.currentTimeMillis();    t.test("pow2recursivo4.txt", 5, 1, 50, "source.Pow2", "pow2Rec4");    j = System.currentTimeMillis();    System.out.println("Fin recursivo4--Tiempo:" + (j-i));}}

Expliquemos las cosas:

• La palabra reservada @Test sirve para indicarle al compilador que ese método forma parte de una JUnit y que debe ser evaluado.
• El método testPow2() { ... } es un método donde probamos que los métodos de la clase Pow2 funcionan correctamente, para ello creamos una nueva instancia de la clase y usamos el método assertEquals(..., ...) de la clase Assert para probar que el parámetro primero es igual al segundo. Si no fuese igual daría un fallo (podéis probarlo).
• Los otros dos métodos sirven para obtener los datos con los que probar los tiempos.

Ejecutando nuestra prueba

Si la ejecutamos veremos que tarda un montón de tiempo. Si vamos donde tengamos el proyecto veremos que nos a creado varios ficheros del tipo linear.txt que contiene una información similar a:

1, 62, 103, 16...25, 13126, 13627, 14228, 14729, 15230, 156

Eso es para un tamaño n (no real) situado en la columna 1 lo que tardará indique a columna 2. En el siguiente archivo Excel podemos ver un desglose de los datos.

Como siempre aquí tenéis el código fuente.