Supongamos que tengo dos listas de enteros positivos de la personalidad limitada, y tomo el producto de todos los elementos de cada lista. ¿Cuál es la mejor manera de determinar qué producto es más grande?
Por supuesto, simplemente puedo calcular cada producto, pero espero que haya un enfoque más eficiente, ya que el número de dígitos en los productos aumentará linealmente con el número de términos, de modo que todo el cálculo sea cuadrático.
Si estuviera agregando en lugar de multiplicar, podría usar una "estrategia de cierre" de agregar incrementalmente entradas de la primera lista y restar de la segunda, evitando la necesidad de calcular las sumas generales (grandes). Las técnicas análogas para productos serían sumar los logaritmos de las entradas, pero el problema ahora es que calcular los registros requiere el uso de aritmética inexacta. ¿A menos que haya alguna forma de demostrar que el error numérico es irrelevante?
fuente
Respuestas:
(Entiendo la descripción del problema para que los números de entrada estén delimitados por una constante, por lo que no rastrearé la dependencia del límite).
El problema se puede resolver en tiempo lineal y espacio logarítmico utilizando sumas de logaritmos. Con más detalle, el algoritmo es el siguiente:
Esto lleva tiempo , y los contadores usan el espacio O ( log n ) , ya que cada contador está limitado por un valor n .O ( n ) O ( logn ) norte
Supongamos que son los números primos debajo del límite O ( 1 ) . Mediante la distribución de cada contador para un número una a los factores primos de un (con multiplicidad apropiado), y restando los recuentos de una lista de la otra lista, se obtiene la siguiente en el tiempo O ( log n ) :pag1, ... , pk O ( 1 ) una una O ( logn )
De lo contrario . Según el teorema de Baker , podemos reducir el límite | Λ | > 2 - C log n para una constante determinada C . Por lo tanto, lo siguiente calcula correctamente el signo de Λ :Λ ≠ 0
fuente