Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności: Wstaw nową liczbę całkowitą Wstaw zakres ciągłych liczb całkowitych Usuń liczbę całkowitą Usuń wszystkie liczby całkowite poniżej liczby całkowitej Sprawdź, czy występuje liczba...
Załóżmy, że mam ukierunkowany wykres z wagami krawędzi narysowanymi z zakresu [1,…,K][1,…,K][1,\dots, K] gdzie KKK jest stałe. Jeśli próbuję znaleźć najkrótszą ścieżkę za pomocą algorytmu Dijkstry , jak mogę zmodyfikować strukturę algorytmu / danych i poprawić złożoność czasu do...
Termin ten spotkałem wiele razy w różnych materiałach edukacyjnych CS: L2 CS162 (UC Berkeley): We / wy mapowane na pamięć L4 CS162 (UC Berkeley): Pliki mapowane w pamięci L24 CS61 (UC Berkeley): „We / wy mapowane na pamięć”: Rejestry sterowania / danych mapowane na przestrzeń adresową...
Potrzebuję pomocy w określeniu funkcji potencjalnej dla stosu maksymalnego, aby wyciąg maksymalny został zakończony w czasie zamortyzowanym . Powinienem dodać, że nie rozumiem potencjalnie tej metody.O ( 1 )O(1)O(1) Wiem, że funkcja wstawiania powinna „płacić” więcej, aby zmniejszyć koszt...
Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy ZAAA. I to można zrobić wO (logn )O(logn)\mathcal{O}(\log n)czas zgodnie z tutorialem tutaj . Jednak nie jestem w stanie udowodnić, że czas na zapytanie jest rzeczywiście O (logn )O(logn)\mathcal{O}(\log n). Ten link (i...
W mojej klasie Java uczymy się o złożoności różnych typów kolekcji. Wkrótce będziemy rozmawiać o drzewach binarnych, o których czytałem. Książka stwierdza, że minimalna wysokość drzewa binarnego wynosi , ale nie oferuje dalszych wyjaśnień.log2( n + 1 ) - 1log2)(n+1)-1\log_2(n+1) - 1 Czy ktoś...
Próbuję zrozumieć, w jaki sposób drzewa indeksowane binarnie (drzewa fenwick) można modyfikować w celu obsługi zapytań o zakres i aktualizacji zakresu. Znalazłem następujące źródła: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
Dla danego płaskiego wykresu osadzonego w płaszczyźnie, zdefiniowanego przez zestaw segmentów liniowych , każdy segment jest reprezentowany przez punkty końcowe . Skonstruuj strukturę danych DCEL dla podziału planarnego, opisz algorytm, udowodnij jego poprawność i pokaż...
Byłem zdezorientowany podczas rozwiązywania następującego problemu (pytania 1–3). Pytanie D -ary sterty jest jak stos binarny, lecz (z wyjątkiem jednej z możliwych) węzły nie liść ma d dzieci zamiast 2 dzieci. Jak byś stanowią d -ary sterty w tablicy? Jaka jest wysokość d -ary sterty n...
Patrzę na techniki implementacji języków programowania, a ostatnio natknąłem się na stosy spaghetti, które podobno dobrze pasują do modelu stylu kontynuacji przechodzenia (biorąc pod uwagę ich zastosowanie np. W Scheme i SML / NJ ). Dla uproszczenia rozważmy tylko jedno-wątkowe procesy dla tego...
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...
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...
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...
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
SkipList zapewnia to samo O(logn)O(logn)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...
Chcę wydajnie filtrować listę liczb całkowitych dla duplikatów w taki sposób, że tylko wynikowy zestaw musi być przechowywany. Można to zobaczyć na jeden sposób: mamy szereg liczb całkowitych S={1,…,N}S={1,…,N}S = \{1, \dots{}, N\} z NNN duży (powiedzmy 2402402^{40}) mamy funkcję f:S→Sf:S→Sf : S...
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...
Chociaż pracuję jako programista w swoim codziennym życiu i używam wszystkich modnych języków (Python, Java, C itp.), Nadal nie mam jasnego obrazu tego, czym jest programowanie funkcjonalne. Z tego, co przeczytałem, jedną właściwością języków funkcjonalnych jest to, że struktury danych są...