Pytania dotyczące sposobów przechowywania danych, aby mogły być korzystnie wykorzystywane przez algorytmy.
Zastanawiam się nad tym pytaniem, odkąd byłem studentem. To pytanie ogólne, ale opiszę poniżej przykłady. Widziałem wiele algorytmów - na przykład dla problemów z maksymalnym przepływem znam około 3 algorytmów, które mogą rozwiązać problem: Ford-Fulkerson, Edmonds-Karp i Dinic, przy czym Dinic ma...
Te dwa wydają się bardzo podobne i mają prawie identyczną strukturę. Co za różnica? Jakie są zawiłości czasowe dla różnych operacji każdego z
Często mówi się, że wyszukiwanie tablicy skrótów działa w stałym czasie: obliczasz wartość skrótu, co daje indeks dla wyszukiwania tablicy. Jednak ignoruje to kolizje; w najgorszym przypadku każdy przedmiot ląduje w tym samym wiadrze, a czas wyszukiwania staje się liniowy ( ).Θ ( n...
Jeśli mam listę kluczowych wartości od 1 do 100 i chcę je uporządkować w szeregu 11 segmentów, nauczono mnie tworzyć funkcję mod H=kmod 11H=kmod 11 H = k \bmod \ 11 Teraz wszystkie wartości zostaną umieszczone jeden po drugim w 9 rzędach. Na przykład w pierwszym segmencie będzie...
Wygląda na to, że gdziekolwiek spojrzę, struktury danych są wdrażane przy użyciu czerwono-czarnych drzew ( std::setw C ++, SortedDictionaryw C # itp.) Właśnie omawiając (a, b), czerwono-czarne i drzewa AVL w mojej klasie algorytmów, oto co wyciągnąłem (również z pytania po profesorach,...
Istnieje wiele struktur danych, które implementują interfejs kolejki priorytetowej: Wstaw: wstaw element do struktury Get-Min: zwraca najmniejszy element w strukturze Extract-Min: usuń najmniejszy element ze struktury Typowe struktury danych implementujące ten interfejs to (min) hałdy...
Załóżmy następującą definicję drzewa czerwono-czarnego: Jest to drzewo wyszukiwania binarnego. Każdy węzeł ma kolor czerwony lub czarny. Korzeń jest czarny. Dwa węzły połączone krawędzią nie mogą być jednocześnie czerwone. Oto dobra definicja liścia NIL, jak na wiki. Liść NIL ma kolor...
Próbuję napisać moduł sprawdzania pisowni, który powinien działać z dość dużym słownikiem. Naprawdę chcę efektywnego sposobu indeksowania danych słownikowych za pomocą odległości Damerau-Levenshteina w celu ustalenia, które słowa są najbliższe błędnie napisanemu słowu. Szukam struktury danych,...
Rozumiem, że „struktura” danych jest całkowicie zależna od Algebry Boolean, ale: Dlaczego dane są uważane za dyskretny byt matematyczny, a nie ciągły? Powiązane z tym: Jakie wady lub niezmienniki są naruszane w strukturze danych jako ciągłej jednostki w wymiarach ?rrr Nie jestem...
Nie jestem nawet studentem CS, więc może to być głupie pytanie, ale proszę o wyrozumiałość ... W erze komputerów wstępnych możemy zaimplementować strukturę danych tablicowych z czymś w rodzaju tablicy szuflad. Ponieważ jeden zlokalizować szuflady z odpowiadającym indeksu przed ekstrakcji wartość z...
Uczę się o drzewach Radix (inaczej skompresowanych próbach) i Patricii, ale znajduję sprzeczne informacje na temat tego, czy faktycznie są one takie same. Drzewo radix można uzyskać z normalnej (nieskompresowanej) trie, łącząc węzły z ich rodzicami, gdy węzły są jedynym dzieckiem. Dotyczy to...
Podczas implementacji słownika („Chcę wyszukiwać dane klientów według ich identyfikatorów klienta”), typowymi stosowanymi strukturami danych są tabele skrótów i drzewa wyszukiwania binarnego. Wiem na przykład, że biblioteka STL C ++ implementuje słowniki (nazywają je mapami) przy użyciu...
Intuicyjnie „zrównoważone drzewa” powinny być drzewami, w których lewe i prawe podgrzewa w każdym węźle muszą mieć „w przybliżeniu taką samą” liczbę węzłów. Oczywiście, gdy mówimy o zrównoważeniu czerwono-czarnych drzew * (patrz definicja na końcu), faktycznie mamy na myśli, że są one zrównoważone...
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita nie była...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
Szukam struktury danych, która przechowuje zestaw ciągów znaków nad zestawem znaków , zdolną do wykonywania następujących operacji. Oznaczmy D ( S ) , jak w strukturze danych przechowującej zestaw łańcuchy S .ΣΣ\SigmaD(S)D(S)\mathcal{D}(S)SSS Add-Prefix-Setna : biorąc pod uwagę pewien zestaw T...
Widziałem dwie definicje zrównoważonych drzew binarnych, które wyglądają inaczej dla mnie. Drzewo binarne jest zrównoważone, jeśli dla każdego węzła utrzymuje, że liczba wewnętrznych węzłów w lewym poddrzewie i liczba wewnętrznych węzłów w prawym poddrzewie różnią się co najwyżej o 1. Drzewo...
Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem...
Filtr Bloom pozwala efektywnie śledzić, czy różne wartości zostały już napotkał podczas przetwarzania. Gdy jest wiele elementów danych, filtr Bloom może spowodować znaczne oszczędności pamięci w tabeli skrótów. Główną cechą filtra Bloom, który dzieli z tabelą skrótów, jest to, że zawsze mówi „nie...
Nie do końca rozumiem, dlaczego rotacja w strukturze danych drzewa splay uwzględnia nie tylko element nadrzędny węzła oceniającego, ale także dziadka (operacja zygzak i zig-zig). Dlaczego następujące elementy nie działają: Gdy wstawiamy na przykład nowy węzeł do drzewa, sprawdzamy, czy wstawiamy...