Porównywanie dwóch produktów z list liczb całkowitych?

Załóżmy, że mam dwie listy liczb całkowitych dodatnich o ograniczonej męskości i biorę iloczyn wszystkich elementów każdej listy. Jaki jest najlepszy sposób ustalenia, który produkt jest większy?

Oczywiście mogę po prostu obliczyć każdy produkt, ale mam nadzieję, że istnieje bardziej wydajne podejście, ponieważ liczba cyfr w produktach wzrośnie liniowo wraz z liczbą terminów, dzięki czemu całe obliczenie będzie kwadratowe.

Gdybym dodawał zamiast zwielokrotniać, mógłbym zastosować „strategię suwaków” polegającą na stopniowym dodawaniu wpisów z pierwszej listy i odejmowaniu od drugiej, unikając potrzeby obliczania (dużych) sum ogólnych. Analogiczne techniki dla produktów polegałyby na sumowaniu logarytmów wpisów, ale problem polega obecnie na tym, że obliczanie logów wymaga użycia niedokładnej arytmetyki. Chyba że istnieje jakiś sposób, aby udowodnić, że błąd numeryczny jest nieistotny?

time-complexity nt.number-theory użytkownik168715
źródło

Jeśli znamy maksymalną liczbę całkowitą i jest ona niezależna od n (tj. Stała k), możemy utworzyć tabelę przeglądową współczynników wszystkich liczb od 1 do k. Teraz myślę, że jeśli napiszesz wszystko w bazie [iloczyn czynników], staje się ono liniowe, ponieważ możesz obliczyć produkty w czasie liniowym z tą bazą, a następnie porównać każdą cyfrę (zaczynając od cyfry najwyższego rzędu) kolejno, aż jedna z nich będzie większa od drugiej. Szczegóły są trochę trudne, ale myślę, że powinno to działać, jeśli k jest stałą.

Phylliida

0

$0$

n

$n$

m

$m$

C (m, m) + C (m, 2 m) + . . . + C (m, (n - 1) m)

$C(m,m)+C(m,2m)+...+C(m,(n-1)m)$

C (x, y)

$C(x,y)$

x

$x$

y

$y$

Może być jakiś sposób na rozszerzenie metody w math.stackexchange.com/a/1081989/10385

xavierm02

O (M (n))

$O(M(n))$

O (n \log n 2^{O (\log^{*} n)})

$O(n\,\log n\,2^{O(\log^*n)})$

Pomyślę o wymaganej dokładności logów. To może być bardziej wydajne.

Emil Jeřábek

Odpowiedzi:

(Rozumiem opis problemu, dlatego liczby wejściowe są ograniczone stałą, więc nie będę śledził zależności od granicy).

Problem można rozwiązać w czasie liniowym i przestrzeni logarytmicznej za pomocą sum logarytmów. Bardziej szczegółowo algorytm wygląda następująco:

Korzystając z liczników binarnych, policz liczbę wystąpień każdego możliwego numeru wejściowego na obu listach.

$O(n)$ $O(\log n)$ $n$

$p_1,\dots,p_k$ $O(1)$ $a$ $a$ $O(\log n)$

$\beta_1,\dots,\beta_k$ $O(\log n)$ $\Lambda:=\sum_{i=1}^k\beta_i\log p_i$

$\beta_1=\dots=\beta_k=0$

$\Lambda\ne0$

| Λ | > 2^{- C \log n}

$|\Lambda|>2^{-C\log n}$

C

$C$

Λ

$\Lambda$

$\sum_{i=1}^k\beta_i\pi_i$ $\pi_i$ $\log p_i$ $m:=C\log n+k+1$

$M(m)$ $m$ $M(m)=O(m\,\log m\,2^{O(\log^* m)})$ $O(m^2)$ $\log p_i$ $m$ $O(M(m)\log m)$ $\sum_i\beta_i\pi_i$ $O(M(m))$ $O(M(m)\log m)\subseteq O(\log n\,\mathrm{poly}(\log\log n))$

$O(n)$

Emil Jeřábek
źródło

Dzięki! Będę musiał omówić szczegóły później, ale wydaje się to bardzo obiecujące!

user168715