Suponha que eu tenha duas listas de números inteiros positivos de manitude limitada e que eu pegue o produto de todos os elementos de cada lista. Qual é a melhor maneira de determinar qual produto é maior?
É claro que posso simplesmente calcular cada produto, mas espero que exista uma abordagem mais eficiente, pois o número de dígitos nos produtos aumentará linearmente com o número de termos, para que todo o cálculo seja quadrático.
Se eu estivesse adicionando em vez de multiplicar, poderia usar uma "estratégia de zíper" para adicionar incrementalmente entradas da primeira lista e subtrair da segunda, contornando a necessidade de calcular as somas globais (grandes). As técnicas análogas aos produtos seriam somar os logaritmos das entradas, mas o problema agora é que a computação dos logs requer o uso de aritmética inexata. A menos que haja alguma maneira de provar que o erro numérico é irrelevante?
fonte
Respostas:
(Entendo a descrição do problema para que os números de entrada sejam delimitados por uma constante, para não rastrear a dependência do limite.)
O problema é solucionável no tempo linear e no espaço logarítmico usando somas de logaritmos. Mais detalhadamente, o algoritmo é o seguinte:
Isso leva tempo e os contadores usam o espaço O ( log n ) , pois cada contador é delimitado por n em valor.O(n) O(logn) n
fonte