Oznacz i . Rozważ funkcję najmniejsza liczba pierwsza niepodzieląca . Łatwo zauważyć, że . I przez zestaw , niech najmniej Prime że nie dzieli każdy z elementów . Mamy górną granicę
Dlatego prosty algorytm brutalnej siły, który wylicza wszystkie liczby od do i sprawdza, czy nie dzieli żadnego elementu , jest wielomianowy i ma złożoność czasową .
Innym sposobem rozwiązania problemu jest obliczenie wszystkich czynników dla każdego elementu i użycie ich w algorytmie brute-force, aby sprawdzić, czy jest odpowiedzią w czasie . Ten algorytm ma złożoność czasową i wykorzystuje pamięć , ponieważ nie musimy obliczać i czynniki przechowywać większą niż . Dla małych i działa lepiej.
Szczegółowo algorytm składa się z dwóch części:
Zbuduj zestaw złożony ze wszystkich czynników wszystkich elementów , tj. Można to zrobić w czasie i pamięci . (Skąd to się bierze? Dla dowolnego elementu , możemy go uwzględnić przy użyciu próbnego faktoryzacji ze wszystkimi liczbami do lub wszystkich liczb pierwszych do , w zależności od tego, który jest mniejszy; dlatego każdy element można uwzględnić w czasie .)
Znajdź minimalną liczbę . Ten krok wymaga czasu , jeśli sprawdza się, czy można wykonać w czasie .
Mam dwa pytania, którymi jestem zainteresowany:
- Czy istnieje szybszy algorytm do rozwiązania problemu?
- W przypadku danych i , w jaki sposób możemy zbudować zbiór z maksymalnym najmniej wspólnym niepodzielnikiem?
źródło
Odpowiedzi:
Możliwe jest ulepszenie drugiego algorytmu poprzez zastosowanie lepszych algorytmów do faktoryzacji liczb całkowitych.
Istotne są tutaj dwa algorytmy faktoryzacji liczb całkowitych:
GNFS może uwzględniać liczbę całkowitą z czasem działania .≤C O(LC[0.33,1.92])
ECM może znaleźć czynniki (jeśli istnieje) z czasem działania ; znalezienie wszystkich czynników zajmie tyle razy (co jest względnie małe w porównaniu z czasem działania ECM).≤nlogC O(LnlogC[0.5,1.41]) O(logC/log(nlogC))
Tutaj .Ln[α,c]=exp{c(logn)α(loglogn)1−α}
To dość przerażająco wyglądające wyrażenie na czas wykonywania, ale ważne jest to, że jest to szybsze niż metody, o których wspomniałeś. W szczególności jest asymptotycznie znacznie mniejszy niż , tzn. GNFS jest znacznie szybszy niż wypróbowanie wszystkich możliwych czynników . Również jest asymptotycznie znacznie mniejsze niż , czyli ECM jest znacznie szybciej niż próbuje wszystkich możliwych czynników .LC[0.33,1.92] C−−√ ≤C−−√ LnlogC[0.5,1.41] nlogC ≤nlogC
Tak więc całkowity czas działania dla tej metody wynosi mniej więcej , a to jest asymptotycznie lepsze niż twoje pierwsza metoda i asymptotycznie lepsza niż druga metoda. Nie wiem, czy da się zrobić jeszcze lepiej.O~(nmin(LC[0.33,1.92],LnlogC[0.5,1.41]))
źródło
Najmniej powszechny niepodzielnik może być tak duży jak N log C, ale jeśli liczby N są losowo rozmieszczone, to najmniej powszechny niepodzielnik jest prawdopodobnie znacznie mniejszy, prawdopodobnie dużo mniejszy niż N. Zbudowałbym tabele, z których liczby pierwsze są dzielnikami, których liczby.
Dla każdej liczby pierwszej p mamy indeks co oznacza, że wszystkie liczby do tego indeksu zostały zbadane pod kątem podzielności przez p, i mamy listę wszystkich tych liczb, przez które można było podzielić.kp
Następnie dla d = 2, 3, 4, ... próbujemy znaleźć liczbę podzielną przez d lub pokazać, że nie ma. Przyjmujemy największy czynnik p p. D. Następnie sprawdzamy wszystkie liczby, które można podzielić przez p, czy są one również podzielne przez d. Jeśli nie zostaną znalezione, sprawdzamy kolejne liczby za pomocą wskaźników> kątem podzielności przez p, aktualizując i listę liczb podzielnych przez p, i sprawdzamy, czy każda liczba jest podzielna przez d.kp kp
Aby sprawdzić, czy istnieje liczba podzielna przez p, sprawdzamy średnie liczby p. Później, jeśli sprawdzimy, czy istnieje liczba podzielna przez 2p, istnieje 50% szansa, że musimy sprawdzić tylko jedną liczbę (tę, która jest podzielna przez p) i 50% szansy na sprawdzenie średnio o 2 p więcej liczb. Znalezienie liczby podzielnej przez 3p jest dość prawdopodobne i tak dalej, i nigdy nie sprawdzamy więcej niż N liczb pod kątem podzielności przez p, ponieważ są tylko N liczb.
Mam nadzieję, że to zadziała z około podzielnościąN2/logN
PS. Jak duży byłby wynik dla liczb losowych?
Załóżmy, że mam N liczb losowych. Prawdopodobieństwo, że jedna z N liczb jest podzielna przez d wynosi 1 - (1 - 1 / d) ^ N. Zakładam, że prawdopodobieństwo, że każda z liczb 1 ≤ d ≤ k jest współczynnikiem jednej z liczb losowych, jest obliczane poprzez pomnożenie tych prawdopodobieństw (Ok, to trochę niepewne, ponieważ te prawdopodobieństwa prawdopodobnie nie są całkiem niezależne).
Przy takim założeniu, przy N = 1000, istnieje 50% szans, że jedna z liczb 1..244 nie podzieli żadnej liczby, a jedna na miliard, że każda liczba do 507 dzieli jedną z liczb. Przy N = 10 000 istnieje 50% szans, że jedna z liczb 1..1726 nie podzieli żadnej liczby, a jedna na miliard, że każda liczba do 2979 dzieli jedną z liczb.
Proponuję, aby dla N losowych danych wejściowych rozmiar wyniku był nieco większy niż N / ln N; może coś w stylu N / ln N * (ln ln N) ^ 2. Dlatego:
Prawdopodobieństwo, że co najmniej jeden z N liczb losowych jest podzielna przez losową d jest . Jeśli d jest w pobliżu N, to wynosi około 1 - exp (-1) ≈ 0,6321. To dotyczy pojedynczego dzielnika; istnieje szansa, że każda z kilku liczb d ≈ N jest dzielnikiem co najmniej jednej z N liczb, są dość wąskie, więc maksymalne d będzie znacznie mniejsze niż N.1−(1−1/d)N 1−(1−1/d)N
Jeśli d << N, to .1−(1−1/d)N≈1−exp(−N/d)
Jeżeli d ≈ N / ln N, a następnie .1−exp(−N/d)≈1−exp(−lnN)=1−1/N
Dodalibyśmy te prawdopodobieństwa dla wartości około N / ln N, ale dla większości d wynik będzie znacznie większy, więc największe d będzie jakoś większe niż N / ln N, ale znacznie mniejsze niż N.
PS. Znajdowanie liczby podzielnej przez d:
Wybieramy największy czynnik p p, a następnie najpierw badamy liczby, o których wiadomo, że są podzielne przez p. Powiedz d = kp. Następnie średnio sprawdzamy tylko liczby k, które są podzielne przez p, podczas sprawdzania tego konkretnego d, i sprawdzamy co najwyżej wszystkie wartości N pod kątem podzielności przez p ogółem, dla wszystkich d podzielnych przez p. W rzeczywistości najprawdopodobniej sprawdzamy mniej niż N wartości dla większości liczb pierwszych p, ponieważ po sprawdzeniu wszystkich N wartości algorytm najprawdopodobniej się kończy. Więc jeśli wynikiem jest R, to oczekuję, że mniejsze niż N wartości zostaną podzielone przez każdą liczbę pierwszą mniejszą niż R. Zakładając, że R ≤ N, to około N ^ 2 / log N kontroli.
PS. Przeprowadzanie niektórych testów
Uruchomiłem ten algorytm kilka razy z N = 1 000 000 liczb losowych> 0. Najmniej powszechny niepodzielnik wynosił od 68 000 do 128 000, przy ogromnej większości przebiegów od 100 000 do 120 000. Liczba podziałów wynosiła od 520 milionów do 1800 milionów, czyli o wiele mniej niż (N / ln N) ^ 2; w większości przypadków wykorzystano od 1000 do 1500 milionów dywizji.
źródło