La complejidad computacional de las operaciones matemáticas tiene una buena tabla. Explicaré lo que pueda. Para sumar y restar, podemos calcular la respuesta dígito a dígito como lo hacen los humanos para obtener una solución de tiempo lineal. Esto es asintóticamente óptimo porque tenemos que leer todos los dígitos de todos modos.
Ahora, digamos que estamos tratando de calcular [matemáticas] A \ veces B [/ matemáticas], donde tanto [matemáticas] A [/ matemáticas] como [matemáticas] B [/ matemáticas] son [matemáticas] n [/ matemáticas] -digit números. Podemos dividir ambos números en [matemáticas] n / 2 [/ matemáticas] mitades de dígitos como esta: [matemáticas] A = A_110 ^ {n / 2} + A_0 [/ matemáticas], [matemáticas] B = B_110 ^ {n / 2} + B_0 [/ matemáticas]. Al distribuir, obtenemos [math] AB = A_1B_110 ^ n + (A_1B_0 + A_0B_1) 10 ^ {n / 2} + A_0B_0 [/ math]. El algoritmo estándar que usan los humanos simplemente calcula [matemáticas] A_1B_1, A_1B_0, A_0B_1, [/ matemáticas] y [matemáticas] A_0B_0 [/ matemáticas]. Si dejamos que [matemática] f (n) [/ matemática] sea el costo de la multiplicación y supongamos que [matemática] f (n) = x ^ a [/ matemática] (que es polinomial) obtenemos:
[matemáticas] f (n) = 4f (n / 2) [/ matemáticas]
[matemáticas] x ^ a = 4 (x / 2) ^ a [/ matemáticas]
[matemáticas] a = 2 [/ matemáticas], entonces un algoritmo de tiempo cuadrático. Esto ignora el costo de combinar nuestros cuatro resultados, pero esas son operaciones de suma, que sabemos que son lineales, por lo que son insignificantes.
Tuvimos que hacer dos multiplicaciones para obtener [matemáticas] A_1B_0 + A_0B_1 [/ matemáticas]. Pero, podemos hacerlo en uno. Tenga en cuenta que [math] (A_1 + A_0) (B_1 + B_0) – A_1B_1-A_0B_0 [/ math] [math] = A_1B_0 + A_0B_1 [/ math]. Tuvimos que encontrar [matemáticas] A_1B_1 [/ matemáticas] y [matemáticas] A_0B_0 [/ matemáticas] para los otros pasos de todos modos, por lo que la única multiplicación adicional que estamos haciendo es [matemáticas] (A_1 + A_0) (B_1 + B_0) [ /mates]. (Tenga en cuenta que eso sigue siendo una multiplicación de dos números [matemáticos] n / 2 [/ matemáticos]). Esto tiene el costo de más sumas y restas, pero conducirá a una mejor complejidad del tiempo. Esta vez, obtenemos:
[matemáticas] f (n) = 3f (n / 2) [/ matemáticas]
[matemáticas] x ^ a = 3 (x / 2) ^ a [/ matemáticas]
[matemáticas] a = \ log_2 3 \ aprox1.59 [/ matemáticas]. Y esta es la complejidad temporal de la multiplicación de Karatsuba.
- Ejecuto un modelo de regresión de Cox con dos variables y luego agrego otra variable a este modelo. Cuando agrego la tercera variable, la dirección de los coeficientes cambia. ¿Cómo puedo interpretar esto?
- ¿Qué quiere decir uno con "Cada base es base 10"?
- ¿Qué tipo de matemáticas necesita más un programador? Sé que depende principalmente del trabajo del programador, pero ¿qué es "debe saber"?
- ¿Qué subcampo o resultado en matemática pura podría ser el próximo en encontrar aplicaciones (sorprendentes) del mundo real?
- Si un problema np-hard se resuelve en tiempo polinómico, ¿es eso una prueba de que p = np o este problema se ha clasificado incorrectamente?
Los algoritmos de multiplicación más rápidos generalizan esta técnica de “división”, e incluso los más rápidos usan transformaciones rápidas de Fourier. Pero por miles de dígitos, Karatsuba probablemente le dará el mejor rendimiento; Los algoritmos más avanzados tienen demasiada sobrecarga.
Y nunca aprendí sobre algoritmos de división, así que realmente no puedo explicarlos 🙁
