Generalnie problem jest dość ciekawy. +1 za danie mi nad czym myśleć. Póki co ucinamy stałe. Zacząłem się zastanawiać, czy dla tego problemu można zejść niżej jeśli chodzi o złożoność asymptotyczną do np. O(nlogn) albo O(n), przy wykorzystaniu np. dodatkowej pamięci. Wyniki moich rozważań nie są do końca jednoznaczne, ale podzielę się nimi. O(n^2) to dobrze znany bruteforce, więc chcielibyśmy co nieco to ulepszyć. Użytkownik enedil nie podał zakresów dla jakich algorytm ma być poprawny, dlatego rozważyłem sam kilka klas abstrakcji w które będzie on mógł wpadać. Przyjmijmy na ten moment, że n jest liczbą liczb, dla których mamy odnaleźć NWD, a v oznacz maksymalną wartość jaką może posiadać pojedyncza liczba.
Należy zauważyć, że algorytm brutalny w takim ujęciu będzie miał złożoność O(n^2 * log(v)), ponieważ policzenie NWD jest także pewnym, niestałym kosztem. Ten koszt możemy też górnie oszacować. Można dowieść, że algorytm Euklidesa wykona najwięcej kroków dla 2 kolejnych liczb Fibonacciego, a co więcej wygenerowana liczba będzie liczbą poprzednią w tym ciągu. Przykładowo rozważmy
a = 34, b = 21
1. a=21 b=13
2. a=13 b=8
3. a=8 b=5
4. a=5 b=3
5. b=3 a=2
6. a=2 b=1
7. a=1 b=0
Koniec
Innymi słowy koszt ten będzie rósł odwrotnie proporcjonalnie do wzrostu wykładniczego. Funkcją odwrotną do funkcji wykładniczej jest logarytm. Przyjmijmy też, że log oznacz logarytm o podstawie 2. Teraz nasze dane podzielmy na 3 klasy abstrakcji 1. n = 10^9, v=10^6 czyli duże n i małe v Tu nasz algorytm naiwny zamrozi komputer na dość długo szacunkowo będzie to (10^9)^2 * log(10^6) = 10^19 operacji 2. n=10^6, v=10^9 odwrotnie Tu będzie to około 3 * 10^13, co też nie można powiedzieć, by było mało 3. n=10^6, v=10^6 i “małe” dane Ponieważ v przez logarytm ma taki mały wpływ i tu otrzymamy całkiem sporo, 10^13 Pierwszy pomysł w oparciu o dodatkową pamięć (dużo pamięci) będzie działał tylko w przypadku małego v (v=10^6) i będzie polegał na faktoryzacji liczb pierwszych. Pierwsze co wykonamy, to algorytm sita, na liczbach 1-v. Jest ich tylko 10^6, więc nie powinno zając to dużo czasu biorąc pod uwagę, że uciąć szukanie możemy na pewnym k = sqrt(v). Wykonanie sita zajmie nam vlog(v). Dla zainteresowanych jak dowieść poprawności przesiewania z ucięciem na sqrt(v) i złożoności link. Jedyną różnicą jaką uzyskamy w stosunku do standardowego sita, jest to, że tablica ta nie będzie zawierać binarnej odpowiedzi na pytanie czy indeks jest/nie jest liczbą pierwszą, ale najmniejszą liczbę pierwszą przez którą ten indeks jest podzielny, dla 1 możemy wybrać cokolwiek, bo nie jest interesująca z punktu widzenia rozkładu. Przykładowy fragment tablicy
index = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
value = 0 2 3 2 5 2 7 2 3 2 11 2 13 2 3
Zauważmy, że teraz faktoryzacja liczby [1-v] jest bajecznie prosta, wystarczy, że wykonamy dzielenie index/a[index] w pętli tk długo jak spełniony jest warunek index != 1. A po drodze spamiętamy wszystkie a[index]. Przykładowo dla 12:
i = 12, a[i] = 2, i/a[i] = 6 (zapamiętaj 2)
i = 6, a[i] = 2, i/a[i] = 3 (zapamięaj 2)
i = 3, a[i]= 3, i/a[i] = 1 (zapamiętaj 3)
i = 1 (koniec)
Nasz rozkład to 2*2*3. Złożoność takiego wyszukania liczby zależy od ilości czynników, a ponieważ tych czynników może być co najwyżej logarytmicznie wiele, to czas rozkładu jednej liczby (mając wcześniej wyliczoną tablicę) wynosi O(log(v)) Okej, tylko co to nam daje? W sumie nic. Musimy zauważyć jeszcze jeden fakt, co najlepiej zrobić na podstawówkowym wyjaśnieniu NWD (z przecinającymi się zbiorami). Stwórzmy jeszcze jedną tablice o rozmiarze v. Od tej pory zastosujemy coś podobnego do counting-sort. Dla każdego i wyliczonego powyżej będziemy zwiększać licznik pod indeksem i o 1. przykładowo, dla 12, nasza tablica wyglądałaby następująco:
index=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count=1 0 1 0 0 1 0 0 0 0 0 1 0 0 0
Teraz dodajmy do tego zbioru jeszcze trochę liczb np. 4, 7, 13, 8, 9, 15, 10. Po przeprowadzeniu ich rozkładu, i uaktualnieniu tablicy, wynik powinien być następujący
index=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count=8 2 2 2 2 1 1 1 1 1 0 1 1 0 1
I teraz nasz max NWD, to pierwsza od prawej pozycja, która jest większa od 1. Tylko dlaczego to działa? Na dobrą sprawę po prostu zapamiętujemy wszystkie liczby generowane przez podzbiory zbioru przecięć, stąd nawiązanie do zbiorów z podstawówki. Warto też zauważyć, że w tym momencie straciliśmy informację, które dwie liczby generują ten maks NWD, oczywiście liniowym przebiegiem, możemy ją odzyskać, ale to nie jest celem zadania. Maks został wyznaczony.
Jaka jest złożoność naszego rozwiązania?
-
Generowanie tablicy czynników sitem: O(v*log(v))
-
Wykonanie rozkładu O(log(v)) i zwiększanie licznika O(1), przy czym robimy to n razy O(n*log(v)) (bo tyle jest liczb na wejściu)
Czyli całość uzyskało złożoność O((n+v)*log(v))
Co przy założeniu, że v=10^6, w obu przypadkach daje lepsze wyniki.
Dla pierwszego będzie to coś około: 10^10
Dla trzeciego: 2 * 10^7
Warto też wziąć poprawkę, na to, że tablicę liczb do rozkładu, możemy precomputować. Co nie zmienia za bardzo asymptotycznie rozwiązania, ale może zmniejszyć widocznie czas działania.
Niestety tego algorytmu nie zastosujemy przy danych rzędu drugiego v=10^9, ponieważ alokacja O(v) pamięci będzie niemożliwa. Pomysł na ulepszenie tego algorytmu przedstawię potem (edytuję post), bo teraz nie mam czasu…
Disclaimer: Rozważanie mogą zawierać jakiś błąd (każdy jest omylny), więc zapraszam do dyskusji =).
). Mam ograniczenie: według Twoich oznaczeń n <= 1 * 10 ^ 5, v <= 1 * 10 ^ 6. Spróbuję to jakoś zaimplementować. BTW nie spodziewałem się po tym zadaniu takiego poziomu abstrakcji 