¿Una herramienta para calcular la complejidad de tiempo del código Java?

Question

Tengo una pregunta sobre la complejidad del tiempo (notación O grande) para el software Java. ¿Hay alguna manera de calcularlo o probarlo rápidamente (o cualquier sitio web que pueda calcularlo para mí sería bienvenido)? Por ejemplo, me gustaría para comprobar que para el siguiente fragmento de código y posiblemente mejorar así:

int dcount = 24423567; 
     int a = 0; 
     if (dcount == 0){ 
      a = 1; 
     } 

     String ds = Integer.toString(dcount); 
     String[] sa = ds.split("(?<=.)"); 
     HashSet hs = new HashSet(); 
     Collections.addAll(hs, sa); 
     a = hs.size(); 
     if (dcount < 0) 
      a--; 

     System.out.println(a); 

Answer 1

Como @emory señaló, es demostrablemente imposible determinar el orden O tiempo de complejidad de una pieza arbitraria de código automáticamente (la prueba es una reducción del Halting Problem). Sin embargo, hay herramientas que pueden intentar medir empíricamente la complejidad de una pieza de código ejecutándola en varias entradas diferentes. Una de esas herramientas se describe en el documento "Measuring Empirical Computational Complexity" de Goldsmith, Aiken y Wilkerson. Funciona al intentar hacer una regresión en el tiempo de ejecución del programa frente a su tamaño de entrada. La herramienta, llamada trend-prof, está disponible en línea.

Espero que esto ayude!

Answer 2

podría estar resolviendo la tarea de alguien, pero la pregunta estaba pidiendo una solución sensata ...

Contando dígitos distintos en un número no requiere de cuerdas, conjuntos o expresiones regulares, sólo algunos aritmética simple.

El siguiente método se ejecuta en tiempo O (n) (n = número de dígitos en la entrada) y espacio constante:

int distinctDigits(int num) { 
    if (num == 0) { 
    return 1; 
    } 

    boolean[] digits = new boolean[10]; 

    while (num > 0) { 
    digits[num % 10] = true; 
    num /= 10; 
    } 

    int count = 0; 
    for (boolean digit : digits) { 
    if (digit) { 
     count++; 
    } 
    } 

    return count; 
} 

Hacer este trabajo para los números negativos se deja como exericse para el lector;)