¿Qué complejidad son operaciones en BigInteger de Java 7?

Question

¿Qué complejidad son los métodos? multiply, divide y pow en BigInteger ¿corrientemente? No se menciona la complejidad computacional en la documentación (ni en ningún otro lugar).

Answer 1

Si miras el código para BigInteger (provisto de JDK), me parece quemultiply(..) posee O (n^2) (en realidad el método es multiplyToLen(..)). El código para los otros métodos es un poco más complejo, pero puedes verte a ti mismo.

Nota: Esto es para Java 6. Supongo que no diferirá en Java 7.

Answer 2

Hay una nueva clase de Biginteger "mejor" que no está siendo utilizada por el Sun JDK para el conservador y la falta de pruebas de regresión útiles (enormes conjuntos de datos). El tipo que hizo los mejores algoritmos podría haber discutido el viejo Biginteger en los comentarios.

Aquí tienes http://futureboy.us/temp/biginteger.java

Answer 3

Mídelo. Realice operaciones con operandos que aumentan linealmente y dibujen los tiempos en un diagrama. No olvide calentar el JVM (varias ejecuciones) para obtener resultados de referencia válidos.

Si las operaciones son lineales o (n), cuadrática o (n^2), polinomio o exponencial debe ser obvio.

Editar: Si bien puede dar algoritmos límites teóricos, es posible que no sean tan útiles en la práctica. En primer lugar, la complejidad no da el factor. Algunos algoritmos lineales o subcuadráticos simplemente no son útiles porque están comiendo tanto tiempo y recursos que no son adecuados para el problema en cuestión (por ejemplo, multiplicación de matriz de Coppersmith-Winograd). Entonces su cálculo puede tener todos los kludges que solo puede detectar por experimento. Hay algoritmos de preparación que no hacen nada para resolver el problema, sino para acelerar el solucionador real (acondicionamiento de la matriz). Hay implementaciones subóptimas. Con longitudes más largas, su velocidad puede caer dramáticamente (faltando en caché, en movimiento de memoria, etc.). Entonces, para fines prácticos, aconsejo hacer experimentación.

Lo mejor es duplicar cada vez la longitud de la entrada y comparar los tiempos. Y si tu hacer Averigüe si un algoritmo tiene n^1.5 o n^1.8 complejidad. Simplemente cuadruplique la longitud de entrada y solo necesita el medio tiempo para 1.5 en lugar de 2. Obtiene nuevamente la mitad del tiempo para 1.8 si multiplica la longitud 256 veces.