Solución:
Como señaló @emory, es demostrablemente imposible determinar la complejidad de tiempo grande de una pieza arbitraria de código automáticamente (la prueba es una reducción del problema de detención). Sin embargo, existen herramientas que pueden intentar medir la complejidad de un fragmento de código empíricamente ejecutándolo en varias entradas diferentes. Una de estas herramientas se describe en el artículo “Midiendo la complejidad computacional empírica” 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(descontinuado), está disponible como referencia.
¡Espero que esto ayude!
Podría estar resolviendo la tarea de alguien, pero la pregunta estaba pidiendo una solución sensata …
Contar dígitos distintos en un número no requiere cadenas, conjuntos o expresiones regulares, solo algunas aritméticas simples.
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 que esto funcione para números negativos se deja como ejercicio para el lector;)