Pytania otagowane jako data-structures

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

5
Jakie są powody uczenia się różnych algorytmów / struktur danych służących temu samemu celowi?
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 najlepszą złożoność. W przypadku struktur danych - na …
4
Dlaczego drzewa czerwono-czarne są tak popularne?
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, przeglądania kilku książek i przeglądania go trochę): Drzewa …
9
Czy istnieje kolejka priorytetowa z wyciągami ?
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 . Zazwyczaj (zamortyzowane) czasy wykonywania tych operacji są następujące: Wstaw: (czasami )O ( log n …
1
Wyobraź sobie czerwono-czarne drzewo. Czy zawsze istnieje sekwencja wstawiania i usuwania, która ją tworzy?
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 czarny. Ścieżka od korzenia do dowolnego liścia NIL zawiera …
2
Wydajne struktury danych do budowy szybkiego sprawdzania pisowni
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, która dałaby mi najlepszy kompromis między złożonością przestrzeni a złożonością środowiska wykonawczego. Na podstawie …
11
Dlaczego dane w informatyce są uważane za dyskretne?
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 ekspertem w tej dziedzinie, ponieważ jestem studentem matematyki …
3
Czy sprzęt / implementacja wpłynie na złożoność algorytmów czas / przestrzeń?
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 niej złożoność czas odnośnika tablicy jest , przy …
2
Jaka jest różnica między drzewami radix a próbami Patricii?
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 również prób Patricii. W jaki sposób dwie …
1
Tabele skrótów a drzewa binarne
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 (zrównoważonych) drzew wyszukiwania binarnego, a platforma .NET używa tabel mieszania pod maską. Jakie …
2
Nie wszystkie drzewa czerwono-czarne są zrównoważone?
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 wysokościowo iw tym sensie są zrównoważone. Załóżmy, …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
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 określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
1
Czy istnieje struktura danych „ciąg znaków”, która obsługuje te operacje na łańcuchach?
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 (prawdopodobnie pustych) ciągów, których rozmiar jest ograniczony stałą, a których …
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.