Предположим, у меня есть два списка положительных целых чисел ограниченной мужественности, и я беру произведение всех элементов каждого списка. Какой лучший способ определить, какой продукт больше?
Конечно, я могу просто вычислить каждый продукт, но я надеюсь, что есть более эффективный подход, так как число цифр в продуктах будет линейно увеличиваться с количеством членов, так что все вычисления будут квадратичными.
Если бы я прибавлял вместо умножения, я мог бы использовать «стратегию молнии», заключающуюся в постепенном добавлении записей из первого списка и вычитании из второго, обходя необходимость вычисления (больших) общих сумм. Аналогичные методы для продуктов будут заключаться в суммировании логарифмов записей, но теперь проблема заключается в том, что для вычисления журналов требуется использование неточной арифметики. Разве есть какой-то способ доказать, что числовая ошибка не имеет значения?
источник
Ответы:
(Я понимаю описание проблемы, так что входные числа ограничены константой, поэтому я не буду отслеживать зависимость от границы.)
Задача разрешима в линейном времени и логарифмическом пространстве с использованием сумм логарифмов. Более подробно алгоритм выглядит следующим образом:
источник