Wzglednie pierwsze

Sprawdź, czy w tablicy A istnieją choć dwa elementy, których wartości są
względnie pierwsze.

Czy istnieje liniowe rozwiazanie tego problemu?

Nie, bo liczba potencjalnych par do sprawdzenia jest kwadratowa.

Dla a będącego liczbą elementów zbioru A oraz m = max(A) istnieje rozwiązanie problemu o złożoności O(a*m).

Jeżeli wiemy, że max(A) < c, mamy rozwiązanie liniowe ;)

Ale nie rozumiem jak to ma dzialac, znajdujemy element najwiekszy i sprawdzamy nwd do tego najwiekszego elementu?

On sobie żartował. Po prostu jeśli zakres liczb jest mały, z góry ograniczony przez stała, to można liczyć sobie nwd dla każdej liczby z zakresu i takie coś niby jest O(1) ;)
ale dla przypadku gdzie zakres liczb i rozmiaru tablicy nie ma ograniczenia to jest nadal kwadratowe.

EDIT: To poniżej może się przydać do zadania "Sprawdź, czy w tablicy A istnieją choć dwa elementy, których wartości nie są względnie pierwsze. " My bad.

@Shalom Właściwie, to nie żartowałem aż tak bardzo ;)

1. Niech m = max(A).
2. Niech P będzie zbiorem liczb pierwszych.
3. Niech P_m = {x ∈ P | x <= sqrt(m)}

niech t będzie tablicą rozmiaru floor(sqrt(m)), stan początkowy każdego elementu to false

dla każdego a ∈ A:
  dla każdego p ∈ P_m:
    jeżeli p | a:
      jeżeli t[p]:
        znaleziono wspólny dzielnik dwóch liczb
      wpp:
        t[p] := true

from functools import *

def primes(n):
  # Returns a list of primes <= n
  return reduce(
    lambda pr, c: pr + [c] if next((0 for d in pr if c % d == 0), 1) else pr,
    range(2, n + 1),
    []
  )

def coprime_integers(xs):
  # Returns True if for every a, b (members of xs) a and b are relatively prime
  # Returns False otherwise
  m = max(xs)
  P = primes(2 << (m.bit_length() >> 1))
  t = [False] * (P[-1] + 1)
  for x in xs:
    for p in P:
      if x % p == 0:
        if t[p]:
          return False
        else:
          t[p] = True
  return True

Kod jest oczywiście poglądowy, implementacja funkcji primes jest nieoptymalna, lista P jest nie mniejsza niż P_m podane w pseudokodzie powyżej.

merlinnot napisał(a):

Jeżeli wiemy, że max(A) < c, mamy rozwiązanie liniowe ;)

W ten sposób każdy problem można sprowadzić do złożoności o(1).

Jest oczywiste, że z normalnym zestawem danych max(A) jest dużo większe niż m, więc twoje założenie jest bardzo życzeniowe.

Poza tym twój algorytm nie ma nic wspólnego z pytaniem.

By wycisnąć złożoność lepszą, niż o(n^2) w zewnętrznej pętli trzeba by było gromadzić jakąś informację na temat wcześniejszych liczb. Na dodatek budowanie i testowanie tej informacji musi mieć złożoność lepszą niż liniowa. Ja nie widzę takiej możliwości,

Teoretycznie można by było mnożyć wszystkie poprzednie liczby i potem sprawdzać czy ten iloczyn jest względnie pierwszy z bieżącą liczbą, ale:

• taka wartość rosła by za szybko powodując, że arytmetyka wielkich liczb zjadła by potencjalny zysk
• sama złożoność algorytmu Euklidesa to o(log (a*b)), więc mnożenie liczb powiększa złożoność testu czy para liczb jest względnie pierwsza
• to jest warunek konieczny, a nie wystarczający, więc i tak nic to nie daje jeśli chodzi o złożoność pesymistyczną.

formalnie rzecz biorąc złożoność wyszukania takiej pary to: o(log(max(A)) * n^2)

Zalozmy, ze mamy tablice N-elemntowa. Robimy sobie mape Map<Integer,Integer> gdzie kluczem jest dzielnik, a wartoscia ilosc wystapien.

1. Iterujemy sie po kazdym elemencie z tablicy // O(n)
   2. Dajmy na to jestesmy pod indeksem i. Iterujemy sie do sqrt(tab[i]) sprawdzajac kolejne dzielniki i inkrementujac licznac w mapie // O(sqrt(n))
2. Iterujemy sie jeszcze raz po tablicy.
   4. Dajmy na to ze jestesmy pod indeksem i. Wartosc w tablicy to x = tab[i].
   5. Iterujemy sie do sqrt(x) zapamietujac wartosci (k,v) gdzie k to dzielnik, v - ilosc wystapen w rozkladzie na czynniki pierwsze
   6. Jesli dla kazdej takiej pary map.get(k) == v to znaczy ze nie istnieje liczba majaca chociaz jeden wspolny czynnik pierwszy
   7. jesli dla kazdej liczby sie okaze ze poprzedni punkt byl nie spelniony to taka para nie istnieje

Zlozonosc : O(N sqrt(N) )

Prawie ;) Bo widzisz sprytnie zakładasz sobie tutaj że rozmiar tablicy -> N oraz największa możliwa liczba w tablicy mają podobny rząd wielkości, co wcale nie jest powiedziane. W rzeczywistości podane rozwiazanie to O(n*sqrt(k)) gdzie n to rozmiar tablicy a k określa liczby które w tablicy sie znajdują. Dla dużych liczb ten algorytm może być znacznie bardziej kosztowny niż naiwne O(n²) bo gcd jest dość "tanie" w porównaniu do faktoryzacji.
Pomijam tu już kwestie taką jak ciche założenie że mamy mapę która ma średni i pesymistyczny czas O(1) kiedy w praktyce mapa na drzewie ma O(logn) a hashmapa pesymistycznie O(n).

Takie gcd to jest swoją drogą jeden z przykładowych "ataków na RSA" -> sama faktoryzacja dużych kluczy (np. >1000 bitów) jest praktycznie niewykonalna póki co, ale jeśli podejrzewamy że generator liczb pierwszych który tworzył klucze był mało losowy to można to wykorzystać. Możemy policzyć gcd między parami kluczy publicznych i liczyć na to że w którejś parze liczba pierwsza sie powtórzy.
To takie praktyczne zastosowanie problemu przedstawionego przez autora ;)

Faktycznie zloznosc to O( N sqrt(K) ) . W zaleznosci od rozmiarów wejścia warto zastanowic sie ktore rozwiazanie jest lepsze. Przykladowo gdy N, K <= 10⁶ to moje rozwiazanie skonczy sie po paru sekundach ( w zaleznosci od komputera ) a N² raczej sie nie skonczy... Z kolei gdy N <= 1000, K<=10¹⁸ to warto wybrac O(N²). Tak chcialem przedstawic tylko inny sposob rozwiazania

Przyjmujac zalozenia takie jak pisalem mozemy zamiast hashmapy uzyc po prostu tablicy o takim rozmiarze bo ilosc czynnikow pierwszych jest proporcjonalna do najwiekszej liczby K.
Hashmapa ma dostep O(1) chyba, ze mamy slaba funkcje hashujaca co powoduje wzrost zlozonosci. Tak btw, to pesymistyczny czas O(log N) a nie O(N) - od javy 1.8 Po 8? elementach w kubelku zamiast linked listy robi sie drzewo