Pytania otagowane jako data-structures

Pytania dotyczące sposobów przechowywania danych, aby mogły być korzystnie wykorzystywane przez algorytmy.

1
Randomized Meldable Heap - Oczekiwana wysokość
Randomizowane zgrzewalne stosy mają operację „łączenie”, której następnie używamy do zdefiniowania wszystkich innych operacji, w tym wstawiania. Pytanie brzmi: jaka jest oczekiwana wysokość tego drzewa nnn węzły? Twierdzenie 1 Gambina i Malinkowskiego, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, ss. 344–349, 1998; …
1
Jaki jest najbardziej wydajny algorytm i struktura danych do utrzymywania informacji o podłączonych komponentach na wykresie dynamicznym?
Powiedzmy, że mam niedokierowany skończony wykres rzadki i muszę być w stanie efektywnie uruchamiać następujące zapytania: IsConnected(N1,N2)IsConnected(N1,N2)IsConnected(N_1, N_2) - zwraca jeśli istnieje ścieżka między i , w przeciwnym razieTTTN1N1N_1N2N2N_2FFF ConnectedNodes(N)ConnectedNodes(N)ConnectedNodes(N) - zwraca zestaw węzłów, które są osiągalne zNNN Można to łatwo zrobić przez wstępne obliczenie połączonych elementów wykresu. Oba zapytania …
3
Kompaktowa reprezentacja ścieżek na wykresie
Mam podzbiór prostych ścieżek na wykresie. Długość ścieżek jest ograniczonaredd. Jaki jest najbardziej zwarty sposób (pod względem pamięci), w jaki sposób mogę reprezentować ścieżki, tak aby nie były reprezentowane żadne inne ścieżki oprócz wybranych? Zauważ, że chcę użyć tej reprezentacji w algorytmie, który będzie powtarzał się przez ten podzbiór ścieżek …
2
Poszukuję zestawu implementacji o małym rozmiarze pamięci
Szukam implementacji ustawionego typu danych. To znaczy musimy utrzymywać dynamiczny podzbiór SSS (wielkościowy nnn) z wszechświata wielkości u zU={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\}uuu operacje insert(x)(dodaj element xdo SSS ) i find(x)(sprawdza, czy element xjest członkiem SSS ). Nie dbam o inne operacje. Dla orientacji, …
1
Splay tree z nieparzystą liczbą obrotów
Podczas wstawiania przedmiotu do drzewa rzutów obroty wykonuje się parami w oparciu o wzór zygzakowaty lub zygzakowaty. Gdy do wykonania jest nieparzysta liczba obrotów, można wykonać dodatkowy obrót, zaczynając od liścia, lub zapisać dodatkowy obrót i zrobić to u podstawy. Czy to ma znaczenie? Na przykład na załączonym obrazie wstawiam …
2
Czy przydatne są probabilistyczne struktury danych wyszukiwania?
SkipList zapewnia to samo O(logn)O(log⁡n)O(\log n)ogranicza wyszukiwanie jako drzewo zrównoważone z tą zaletą, że ponowne zbalansowanie nie jest konieczne. Ponieważ SkipList jest konstruowany przy użyciu losowych rzutów monetą, granice te obowiązują tylko tak długo, jak długo struktura SkipList jest wystarczająco „zrównoważona”. W szczególności z prawdopodobieństwem1/nc1/nc1/n^c dla jakiejś stałej c>0c>0c>0, zrównoważona …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.