Supongamos que queremos hacer un programa de computadora que calcule [matemáticas] x ^ y [/ matemáticas]. Una forma simple es hacer un bucle y multiplicar con x de esta manera
def pow (x, y):
ans = 1
para i en rango (y): #repeat y times
ans = ans * x
volver ans
Pero este programa no es eficiente en términos de complejidad de tiempo (aquí el número de multiplicaciones realizadas) que es [matemática] O (y) [/ matemática]
- ¿Necesito matemáticas para programar?
- Cómo convertir 25 cm a mm sin usar una regla
- ¿Cuánto CS se enseña en matemáticas y la rama de computación en ISM y BHU?
- ¿Cómo ayuda el conocimiento matemático en la programación? ¿Puedes describir algunos ejemplos?
- ¿Cuál es la diferencia entre la informática teórica y las matemáticas discretas?
Podemos mejorar el tiempo considerando un simple hecho de que
[matemáticas] x ^ y = x ^ {y / 2} * x ^ {y / 2} [/ matemáticas] si y es un número par
[matemáticas] x ^ y = x ^ {y / 2} * x ^ {y / 2} * x [/ matemáticas] más para números impares
donde y / 2 significa el número entero más grande que es menor o igual que y / 2 (por ejemplo: 7/2 = 3, 21/2 = 10, 10/2 = 5)
Si quisiéramos calcular [matemáticas] x ^ {y / 2} [/ matemáticas] y almacenarlo en [matemáticas] una variable [/ matemáticas] es decir: [matemáticas] x ^ y = a * a [/ matemáticas] entonces con una multiplicación podríamos haber obtenido nuestro resultado, esto implica que con una multiplicación podemos reducir la complejidad de encontrar la potencia de y a y / 2.
Entonces, en [math] O (log_2 (y)) [/ math] pasos o multiplicaciones, podemos calcular [math] x ^ y [/ math]
- [matemáticas] por ejemplo: 2 ^ {16} = a * a [/ matemáticas] donde [matemáticas] a = 2 ^ 8 [/ matemáticas]
- [matemáticas] 2 ^ 8 = b * b [/ matemáticas] donde [matemáticas] b = 2 ^ 4 [/ matemáticas]
- [matemáticas] 2 ^ 4 = c * c [/ matemáticas] donde [matemáticas] c = 2 ^ 2 [/ matemáticas]
- [matemáticas] 2 ^ 2 = d * d [/ matemáticas] donde [matemáticas] d = 2 [/ matemáticas]
Este ejemplo es en la consideración de que y es una potencia de 2. Pero si no es el caso, también podemos hacer el mismo procedimiento con un ligero cambio.
- [matemáticas] por ejemplo: 2 ^ {15} = a * a * 2 [/ matemáticas] donde [matemáticas] a = 2 ^ 7 [/ matemáticas]
- [matemáticas] 2 ^ 7 = b * b * 2 [/ matemáticas] donde [matemáticas] b = 2 ^ 3 [/ matemáticas]
- [matemáticas] 2 ^ 3 = c * c * 2 [/ matemáticas] donde [matemáticas] c = 2 [/ matemáticas]
Entonces el programa puede reescribirse como
def pow (x, y):
si y == 0:
volver 1
tmp = pow (x, y / 2)
si y% 2 == 0: # maneja incluso el caso de energía
volver tmp * tmp
más: # maneja el caso de poder extraño
volver tmp * tmp * x
La complejidad temporal del programa varía entre [matemática] log_2 (y) [/ matemática] y [matemática] 2 * log_2 (y) [/ matemática] ==> [matemática] O (log_2 (y)) [/ matemática] pero aún es mucho más eficiente que [math] O (y) [/ math]. El concepto utilizado aquí se conoce como exponenciación binaria.
