Сравнивая два произведения списков целых чисел?

10

Предположим, у меня есть два списка положительных целых чисел ограниченной мужественности, и я беру произведение всех элементов каждого списка. Какой лучший способ определить, какой продукт больше?

Конечно, я могу просто вычислить каждый продукт, но я надеюсь, что есть более эффективный подход, так как число цифр в продуктах будет линейно увеличиваться с количеством членов, так что все вычисления будут квадратичными.

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

user168715
источник
Если мы знаем максимальное целочисленное значение, которое не зависит от n (т. Е. От константы k), то мы можем составить таблицу коэффициентов всех чисел от 1 до k. Теперь я думаю, что если вы напишите все в базе [произведение факторов], она станет линейной, поскольку вы можете вычислять продукты в линейном времени с этой базой, а затем сравнивать каждую цифру (начиная с цифры высшего порядка) по очереди, пока одна из них не станет больше другой. Детали там немного сложнее, но я думаю, что это должно работать, если k является константой.
Филлида
0nmC(m,m)+C(m,2m)+...+C(m,(n1)m)C(x,y)xy
1
Может быть какой-то способ расширить метод в math.stackexchange.com/a/1081989/10385
xavierm02
O(M(n))O(nlogn2O(logn))
2
Я подумаю о необходимой точности для логов. Это на самом деле может быть более эффективным.
Эмиль Йержабек

Ответы:

6

(Я понимаю описание проблемы, так что входные числа ограничены константой, поэтому я не буду отслеживать зависимость от границы.)

Задача разрешима в линейном времени и логарифмическом пространстве с использованием сумм логарифмов. Более подробно алгоритм выглядит следующим образом:

  1. Используя двоичные счетчики, подсчитайте количество вхождений каждого возможного входного номера в обоих списках.

O(n)O(logn)n

p1,,pkO(1)aaO(logn)

  1. β1,,βkO(logn)Λ:=i=1kβilogpi

  2. β1==βk=0

Λ0

|Λ|>2Clogn
CΛ
  1. i=1kβiπiπilogpim:=Clogn+k+1

M(m)mM(m)=O(mlogm2O(logm))O(m2)logpimO(M(m)logm)iβiπiO(M(m))O(M(m)logm)O(lognpoly(loglogn))

O(n)

Эмиль Йержабек
источник
Спасибо! Я должен буду проработать детали позже, но это кажется очень многообещающим!
user168715