Algorytm wyszukwania elementów

Mam taki problem:

są dwie tablice(obie po n elementów - kazdy element w danej tablicy jest rózny). Moim zadaniem jest obliczenie ile jest par takich samych elementów np. dla tablic

int t1[5]={1,5,3,8,9};
int t2[5]={2,3,8,5,7};

wynik to 2(bo jest para 3 i 5). Zastanawiałem się, czy jest szybszy algorytm niz n^2. Doszedłem do wniosku, ze można posortowac obie tablice (2nlogn), a nastepnie uzyc wyszukiwania binarnego dla kazdej z liczb(n*logn) czyli laczna zlozonosc to 3nlogn. Czy da się jeszcze go jeszcze ulepszyc?

Ciężko pobić O(nlogn) bez dodatkowych założeń.

Jeśli jednak elementy w obydwu tablicach są całkowite i w rozsądny sposób ograniczone, to możesz uzyskać złożoność liniową ze względu na liczbę elementów w tablicach oraz pamięciową O(m) ze względu na wartość największego elementu w tablicy.

Tworzysz tablicę z ilością wystąpień liczby i. Liczby, których częstość wystąpienia > 1 stanowią Twoje

for (int i=0; i<t2.length; i++) freq[t2[i]]++;
for (int i=0; i<t1.length; i++) freq[t1[i]]++;
for (int i=0; i<freq.length; i++)
 if (freq[i]>1) then wypisz(i);

Jeśli możliwe wartości dla liczb w tablicy są duże, zostaje opcja z haszowaniem wartości i zliczaniem ich częstości. Później możesz operować na listach znacznie krótszych niż wejściowe. W pesymistycznym wypadku jednak i tak niewiele wskórasz ;-)

dzieki bardzo za odpowiedz

fakt, ten algorytm ma pewny mankament - przy tablicy

int tab[2]={1,10000};

bedzie az 10000 operacji dominujących

a chciałbym się dowiedziec, jaka bedzie zlozonosc takiego algorytmu? 2*n+nlogn?

załózmy ze freq[] jest mapą z STL

map<int, int> freq;

for (int i=0; i<t2.length; i++) freq[t2[i]]++;
for (int i=0; i<t1.length; i++) freq[t1[i]]++;
for (int i=0; i<freq.length; i++)
if (freq[i]>1) then wypisz(i);

ups, blad sie wkradl;p
nie powinno byc ostatniej pętli tylko przeszukiwanie mapy iteratorem

Zamiast iterowac po wszystkich indeksach, mozesz iterowac po elementach tablic wejsciowych i sprawdzac tylko indeksy z owych tablic, np. majac {1,2,3,1000} i {2,3,4000}

Otrzymasz tablice t[1..4000] wypelniona glownie zerami oraz taka, ze:
t[1]=1
t[2]=2
t[3]=2
t[1000]=1
t[4000]=1

Nie musisz iterowac po 1..4000, tylko po elementach wejsciowych tablic, czyli {1,2,3,1000,2,3,4000}. Mozesz tez czyscic czestosc wystapien, tak by uniknac duplikatow.

for i in {1,2,3,1000,2,3,4000} do
  if (t[i]>1) then
     wypisz(t[i]);
     t[i]:=0;
done;

W ten sposob otrzymujesz zlozonosc O(n) ze wzgledu na operacje dominujaca "odwloanie po indeksie".

yarel napisał(a)

Zamiast iterowac po wszystkich indeksach, mozesz iterowac po elementach tablic wejsciowych i sprawdzac tylko indeksy z owych tablic, np. majac {1,2,3,1000} i {2,3,4000}

...

Mała poprawka. Przy sprawdzaniu częstości wystarczy iterować po elementach jednej z wejściowych tablic.

lksarp napisał(a)

Doszedłem do wniosku, ze można posortowac obie tablice (2nlogn), a nastepnie uzyc wyszukiwania binarnego dla kazdej z liczb(n*logn) czyli laczna zlozonosc to 3nlogn. Czy da się jeszcze go jeszcze ulepszyc?

Można obyć się bez wyszukiwania binarnego.

1. Sortujemy obie tablice (http://www.cppreference.com/cppalgorithm/sort.html). Wybieramy z obu tablic elementy
2. Przechodzimy po obu tablicach mając dwa wskaźniki podobnie jak to się robi przy scalaniu tablic w sortowaniu przez scalanie. Jeżeli elementy w obu tablicach są równe to zwiększ liczbę par o jeden i przesuń oba wskaźniki o 1, wpp. przesuń wskaźnik wskazujący na mniejszą liczbę.

Po posortowaniu tablic wyszukiwanie binarne jest mało wydajnym algorytmem wyszukiwania par takich samych elementów.
[Ehh... dopiero po napisaniu zauwarzyłem, że ktoś już tą metodę zasugerował]Załóżmy, że mamy 2 posortowane tablice t1 i t2:

1. i1, i2 niech wskazują na aktualnie sprawdzane 2 elementy. i1=i2=1;
2. Jeżeli t1[i1]=t2[i2]:
   -2.true: Zaznaczamy połączenie. i1++;i2++;
   -2.false: Jeżeli t1[i1]>t2[i2] to i2++; w przeciwnym przypadku i1++;
3. Jeżeli i1<=t1.size i i2<=t2.size wracamy do punktu 2
   Prosty algorytm o złożoności <n;2n> :)
   W efekcie końcowym osiągniemy złożoność 2(nlogn+n).

Przychodzi mi do głowy też inny algorytm. Nie sortujemy tablic na początku. Nie chce mi się go opisywać, ale przedstawię metodę o podobnej złożoności:

1. Zapisujemy obydwie tablice w tablicy rekordów/struktur (v:wartość; s(source):numer tablicy z której pochodzi, pos:pozycja w tablicy z któej pochodzi).
2. Sortujemy tą tablicę względem wartości (nlog2n=nlogn+n)
3. Wyszukujemy w tablicy 2 kolejnych elementów o tej samej wartości (2n-1).
   Da się też ten algorytm zapisać z pominięciem punktu pierwszego, aczkolwiek jest on wtedy dużo bardziej skomplikowany, ale jeżeli bardzo zależy panu na wydajności, to radzę się postarać. Przypuszczam że złożoność byłaby o n mniejsza(nie wspominając o całej zamianie struktury danych). Według mojego wyobrażenia wyglądałoby to mniej więcej jak zlepione sortowanie 2 tablic na raz.

UWAGA! Jeżeli chcecie korzystać z tych algorytmów również w innych sytuacjach, pamiętajcie o założeniu, że w tablicach nie ma powtarzających się elementów.