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!
[Algorytmy] Dwa elementy tablic T1 i T2 dające sumę x
-
- Użytkownik
- Posty: 3
- Rejestracja: 21 mar 2015, o 20:08
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 3 razy
[Algorytmy] Dwa elementy tablic T1 i T2 dające sumę x
Ostatnio zmieniony 22 mar 2015, o 08:59 przez Afish, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
-
- Użytkownik
- Posty: 1384
- Rejestracja: 26 lis 2006, o 21:34
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 33 razy
- Pomógł: 268 razy
[Algorytmy] Dwa elementy tablic T1 i T2 dające sumę x
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
Mam nadzieję, że nasunąłem jakiś pomysł.
Pozdrawiam
Ostatnio zmieniony 22 mar 2015, o 09:00 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 311
- Rejestracja: 30 gru 2011, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: Puławy
- Podziękował: 11 razy
- Pomógł: 53 razy
[Algorytmy] Dwa elementy tablic T1 i T2 dające sumę x
Pomysł dobry, złożność będzie się zgadzać. Opisany algorytm to nic innego jak wykonanie \(\displaystyle{ n}\) razy wyszukiwania binarnego.mostostalek pisze: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
-
- Użytkownik
- Posty: 3
- Rejestracja: 21 mar 2015, o 20:08
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 3 razy
[Algorytmy] Dwa elementy tablic T1 i T2 dające sumę x
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?
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?
Ostatnio zmieniony 23 mar 2015, o 16:01 przez Afish, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach