[Algorytmy] Dwa elementy tablic T1 i T2 dające sumę x

[dasdri]

Witam serdecznie!

Na wstępie opiszę problem:
Dana jest liczba x oraz dwie tablice (\(\displaystyle{ T_1}\) oraz \(\displaystyle{ T_2}\)), zawierające \(\displaystyle{ n}\) liczb. Zadaniem jest opracowanie algorytmu który sprawdza czy istnieje para elementów:
\(\displaystyle{ a+b=x}\)
gdzie:
\(\displaystyle{ a \in T_1\\
b \in T_2}\)

Algorytm ma działać ze złożonością \(\displaystyle{ O \left( n\log n \right)}\). Zrealizowałem algorytm działający ze złożonością \(\displaystyle{ n^{2}}\) (pętla w pętli - liczące od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\)), co nie było zbyt trudnym wyzwaniem, jednak nie mam pomysłu jak go zoptymalizować, tak by działał w zadanej złożoności. Myślałem nad tym by najpierw tablice sortować przy użyciu np. quicksorta i pomijać w iteracjach elementy, których wartość jest równa bądź większa od \(\displaystyle{ x}\). Jednak takie podejście byłoby właściwe jedynie w przypadku gdy liczby przechowywane w tablicach nie mogłyby być ujemne, co w poleceniu nie zostało określone.
Proszę o jakieś wskazówki.

Dziękuję i pozdrawiam!

[mostostalek]

Nie wiem za wiele o złożoności algorytmów, ale gdybyś posortował drugą tablicę to dla każdego elementu z pierwszej tablicy mógłbyś sprawdzać tylko część elementów z drugiej biorąc np na początek środkowy element, następnie jeśli suma jest większa od \(\displaystyle{ x}\) to element o indeksie \(\displaystyle{ \frac{n}{4}}\) a gdy mniejsza to element o indeksie \(\displaystyle{ \frac{3n}{4}}\) i tak zagęszczać aż nie przeszukasz całej tablicy (tzn tylko jej części bo ponad połowę pominiesz).
Mam nadzieję, że nasunąłem jakiś pomysł.

Pozdrawiam

[gryxon]

Nie wiem za wiele o złożoności algorytmów, ale gdybyś posortował drugą tablicę to dla każdego elementu z pierwszej tablicy mógłbyś sprawdzać tylko część elementów z drugiej biorąc np na początek środkowy element, następnie jeśli suma jest większa od \(\displaystyle{ x}\) to element o indeksie \(\displaystyle{ \frac{n}{4}}\) a gdy mniejsza to element o indeksie \(\displaystyle{ \frac{3n}{4}}\) i tak zagęszczać aż nie przeszukasz całej tablicy (tzn tylko jej części bo ponad połowę pominiesz).
Mam nadzieję, że nasunąłem jakiś pomysł.

Pozdrawiam

Pomysł dobry, złożność będzie się zgadzać. Opisany algorytm to nic innego jak wykonanie \(\displaystyle{ n}\) razy wyszukiwania binarnego.

[dasdri]

Dziękuję bardzo za odpowiedzi.
Udało mi się zrealizować zaproponowany algorytm, wszystko działa poprawnie. Mam jednak pytanie co do złożoności: docelowa złożoność ma wynosić \(\displaystyle{ O \left( n\log n \right)}\). Złożoność samego sortowania quicksort wynosi właśnie \(\displaystyle{ n\log n}\) - a do tego dochodzi jeszcze algorytm szukający pary liczb, o złożoności również równej \(\displaystyle{ n\log n}\). Czy końcowa złożoność nie będzie wynosić dla całego algorytmu \(\displaystyle{ 2n\log n}\)? Czytałem o notacji dużego \(\displaystyle{ O}\), o tym, że podaje się tylko ten składnik funkcji, który rośnie najszybciej. Co w sytuacji jeśli występują dwa identyczne składniki?

[ksisquare]

Wielkie "O" połknie stałą.

[dasdri]

Rozumiem, jeszcze raz dziękuję za odpowiedzi!