Algorytm sprawdzający, czy w tablicach S i T są liczbami całkowitymi s i t, więc s + t = k, jeśli k ma numer

Question

Próbuję utworzyć algorytm, który pobiera dwie tablice, S i T n liczb całkowitych i całkowitą k. Algorytm sprawdza, czy tablice mają liczby całkowite s i t, więc s + t = k. (S w S i t w T.) Algorytm powinien mieć czas działania O (n log n).

Próbowałem wymyślić coś, co sortuje tablicę T i używam pętli, aby przejść przez S i używam wyszukiwania binarnego, aby sprawdzić, czy znajdę liczbę całkowitą jak k - S [i] dla każdego elementu w S. Ale to zawsze będzie miało czas działania jest większy niż n log n, myślę.

Nie szukam kogoś, kto napisze kod. Tylko pytam tutaj, aby uzyskać pewne pomysły.

Answer 1

Sortuj dwie listy, to jest O (n log n).

Następnie skonfiguruj dwa Iteratory. Jeden iterator zaczyna się od wartości najniższej wartości w S i przechodzi do przodu poprzez stale rosnące wartości w S. Drugi iterator zaczyna od wartości najwyższy w T i iteruje przez ciągle malejące wartości.

Powtórz czynności:

• jeśli aktualne wartości sumują się do liczby większej niż k, awansować iteracyjnej T. To powinno zmniejszyć sumę.
• jeśli bieżące wartości sumują się do liczby mniejszej niż k, należy wykonać iterację S. To powinno zwiększyć sumę.
• jeśli bieżące wartości sumują się na k, a następnie zakończ z powodzeniem.

Ta druga faza powinna spowodować najwyżej 2N, a więc O (n). Tak więc całkowita złożoność to O (n log n).

Ma tę samą złożoność co wielokrotne wyszukiwanie binarne, ale ten algorytm powinien być szybszy, szczególnie w przypadku dużego n.

Answer 2

Algorytm, który określiłeś, faktycznie ma środowisko wykonawcze O (n log n), przy założeniu, że całkowita liczba elementów w obu tablicach to O (n). Można to zobaczyć tutaj:

• Sortuj jedna z tablic (O (n log n))
• Dla każdego elementu drugiej tablicy: (O (n) iteracje)
  • Czy binarne wyszukiwania, aby zobaczyć, czy element komplementarny w drugiej tablicy (o (log n))

pierwszy etap wymaga czasu o (n log n), a drugi etap polega na o (n) iteracji algorytmu O (log n), który w związku z tym zajmuje również czas O (n log n). Ponieważ O (n log n) + O (n log n) = O (n log n), twój algorytm działa w czasie O (n log n). Wygląda na to, że masz dokładnie taki algorytm, jakiego szukasz!

Mam nadzieję, że to pomoże!

Answer 3

Twoje podejście wydaje się być poprawne; najpierw sortuj tablice, dwie operacje O (n log n), a następnie wykonuj n przeszukiwań binarnych, każda o wartości O (log n).

Answer 4

Sortowanie to O (n log n). Następnie dla każdego z elementów O (n), masz wyszukiwanie O (log n) dla pasującego elementu. To brzmi jak O (n log n) w sumie (od O (f) + O (f) = O (f) dla dowolnej funkcji f).

Answer 5

Sortuj zarówno tablice. Przejdź przez nie w kierunku pod kierunkiem. Jeśli suma dwóch elementów jest mniejsza niż k awans, wskaźnik "zwiększający", jeśli jest większy niż k, ustaw wskaźnik zmniejszający. Ta metoda może być nieco wolniejsza niż sortowanie tylko jednej z tablic, ale ostateczne przejście jest zdecydowanie szybsze. I prawdopodobnie krótszy, ponieważ część głowy i ogona z dwóch tablic można pominąć (odciąć).

Answer 6

Jeszcze inna metoda: przechowuj jedną z tablic w tablicy hashtable (O (N)). Wykonaj przejście liniowe przez inne (O (N)) i dla każdego elem wykonaj wyszukiwanie dla k-elem w hashtable. Całkowity czas działania: 2 * O (N): = O (N). Zysk!