Dostajesz zestaw interwałów S. Musisz znaleźć wszystkie interwały w S, które są zawarte w danym przedziale (a, b) w minimalnym czasie złożoności

Dostajesz zestaw interwałów S. Musisz znaleźć wszystkie przedziały w S, które są zawarte w danym przedziale (a, b) w minimalnej złożoności czasu.Dostajesz zestaw interwałów S. Musisz znaleźć wszystkie interwały w S, które są zawarte w danym przedziale (a, b) w minimalnym czasie złożoności

Można to zrobić w czasie O(n) przez brute force, gdzie n to liczba przedziałów w zestawie S. Ale jeśli mogę wykonać pewne wstępne przetwarzanie, można to zrobić w czasie krótszym niż O(n) np. O(log n) czas?

Początkowo myślałem o interval tree, ale nie sądzę, że jest tu zastosowania, ponieważ drzewo przedziałowe stosowany jest, aby wszystkie przedziały że pokrywa z danego przedziału.

Źródło

2013-08-10 Steve M

Jak stwierdzono, najlepiej można zrobić, to 'O (n)' bo w najgorszym przypadku, wszystkie elementy 's' musi zostać skopiowany do wyjścia. –

Tak, to prawda. Miałem jednak nadzieję na coś w rodzaju O (logn) + O (m), gdzie m jest liczbą elementów na wyjściu. –

@SteveM należy również zauważyć, że pod względem dużej notacji O, 'O (logn) + O (m) = O (n)', ponieważ m może być tak duże jak n. Wstępny czas przetwarzania jest również dołączany do środowiska wykonawczego, ponieważ jeśli chcesz posortować przedziały lub ułożyć je przy użyciu pewnych struktur danych, to są one również częścią twojego algorytmu. – Fallen

Możesz zmienić swój problem na płaszczyźnie 2D. Niech (begin, end) każdego interwału będzie punktem dwuwymiarowym. (Zauważ, że wszystkie ważne odstępy skończy się powyżej przekątnej)

Twój Interval-search-problemu przekształca się dobrze studiował prostopadłym zakresie 2D odpytuje z algorytmami, które mają $O(sqrt(n)+k)$ lub $O(log^2+n +k)$ czas pracy, gdzie k jest liczbą punktów zgłaszane.

range query

Źródło

2013-08-10 09:07:53

Niezły pomysł, ale nie znam algorytmu o złożoności mniejszej niż O (k), gdzie k to liczba zgłoszonych punktów. Tak więc Patricia ma rację. – Matthias

Tak, to prawda. Zaktualizowałem swoją odpowiedź, dodając opis k. Ale czasami dane są ładnie dystrybuowane, a twoje zapytania obejmują tylko niewielki zestaw, więc amortyzowany k << n. –

Persistent binary search tree można użyć tutaj.

Pre-processing:

Tworzenie pustego trwałe drzewo. Powinien przechowywać interwały posortowane według punktów końcowych.
Sortuj interwały według ich punktów początkowych.
Dla każdego interwału, zaczynając od końca posortowanej listy, utwórz "kopię" trwałego drzewa i dodaj ten odstęp do tej kopii.

Szukaj:

Znajdź punkt przedziału zapytań w posortowanej liście startowej.
Powtórz odpowiednią "kopię" drzewa trwałego od najmniejszego klawisza do końca interwału zapytania.

Złożoność czasu wyszukiwania to O (log (n) + m), gdzie m to liczba elementów na wyjściu.

Źródło

2013-08-10 08:45:28

Wydaje się, że jego złożoność przestrzenna to O (n^2). Proszę, popraw mnie jeśli się mylę. –

@SteveM: Złożoność przestrzeni to O (n * log (n)). Trwałe struktury danych pozwalają tworzyć płytkie "kopie", w których większość danych jest dzielona między "kopiami", więc każda aktualizacja BST wymaga tylko O (log (n)) dodatkowych węzłów. –

Dostajesz zestaw interwałów S. Musisz znaleźć wszystkie interwały w S, które są zawarte w danym przedziale (a, b) w minimalnym czasie złożoności

Odpowiedz

Powiązane problemy