Pytania otagowane jako ds.data-structures

Właściwości i zastosowania struktur danych, takie jak dolne granice przestrzeni lub złożoność czasowa wstawiania i usuwania obiektów.

2
Czy tradycyjna analiza filtrów Bloom jest nieprawidłowa?
Artykuł ten twierdzi, że tradycyjna analiza poziomu błędu w filtrach Blooma jest nieprawidłowa, a następnie przedstawia długą i niepraktyczną analizę rzeczywistego poziomu błędu. Powiązany artykuł został opublikowany w 2010 r., Ale widziałem, że tradycyjna analiza filtrów Blooma jest nadal nauczana w ramach różnych kursów algorytmów i struktur danych. Czy tradycyjna …
3
Scalenie dwóch drzew wyszukiwania binarnego
Szukam algorytmu do połączenia dwóch drzew wyszukiwania binarnego o dowolnej wielkości i zakresie. Oczywisty sposób byłoby przejść o wdrażaniu tego byłoby znaleźć całe poddrzewa, których zakres można dopasować do dowolnego węzła zewnętrznego w drugim drzewie. Jednak najgorszy czas działania tego typu algorytmu wydaje się być w kolejności, O(n+m)gdzie ni msą …
3
Zwięzłe badanie struktur danych?
Artykuł Fischera w tym miesiącu przypomniał mi, jak mało wiem o sztuce zwięzłych struktur danych i algorytmów ich używania. Dla tych, którzy nie wiedzą o zwięzłych strukturach danych: Biorąc pod uwagę kombinatoryczną strukturę, z (n) odrębnymi konfiguracjami i znaną „użyteczną” reprezentacją . Czy istnieje „zwięzła” struktura danych, która wymaga przechowywania …
3
Ładowanie struktury palca
Po dłuższej pracy z 2-3 palcami jestem pod wrażeniem ich szybkości w większości operacji. Jednak jedynym problemem, na jaki natknąłem się, jest duży koszt związany z początkowym utworzeniem dużego drzewa palców. Ponieważ budowanie jest definiowane jako sekwencja operacji konkatenacji, kończy się budowanie dużej liczby niepotrzebnych struktur drzewa palcowego. Ze względu …
1
Skróty filtra Bloom: więcej czy więcej?
Podczas wdrażania filtra Bloom tradycyjne podejście wymaga wielu niezależnych funkcji skrótu. Kirsch i Mitzenmacher pokazali, że tak naprawdę potrzebujesz tylko dwóch, a resztę możesz wygenerować jako kombinacje liniowe. Moje pytanie brzmi: jaka tak naprawdę jest różnica między dwiema funkcjami skrótu i ​​jedną z podwójną entropią? Wynika to z patrzenia na …
2
Godne uwagi przykłady idei pierwiastka kwadratowego w analizie złożoności
Istnieje wiele algorytmów i struktur danych, które wykorzystują ideę, że otrzymuje minimalną wartość przy k = \ sqrt n . Typowe przykłady to k = √max{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algorytm gigantycznego kroku dziecka do obliczania logarytmu dyskretnego w O(n−−√)O(n)O(\sqrt n) , statyczne zliczanie zakresu ortogonalnego 2D w czasie O(n−−√)O(n)O(\sqrt n) …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
2
Jaka trwała struktura danych dla zestawu częściowo uporządkowanych elementów?
Muszę przechowywać zestawy elementów typu a. Typ a jest częściowo uporządkowany, więc porównanie i może zwrócić mniejsze, większe, równe lub nieporównywalne.a 2za1za1a_1za2)za2)a_2 Jednym z problemów z tablicami skrótów jest to, że dwa równe elementy mogą być reprezentowane w różny sposób i nie mam dostępu do funkcji haszującej zgodnej z równością. …
1
Potrzebujesz dobrego przeglądu algorytmów zwięzłej struktury danych
(już pytałem na głównej stronie , ale proszę również tutaj o lepszy zasięg, przepraszam) Ponieważ wiedziałem o zwięzłych strukturach danych, rozpaczliwie potrzebuję dobrego przeglądu najnowszych osiągnięć w tej dziedzinie. Poszukałem google i przeczytałem wiele artykułów, które mogłem zobaczyć na górze wyników wyszukiwania Google na prośby z góry mojej głowy. Nadal …
1
Ponowne użycie 5 niezależnych funkcji skrótu do sondowania liniowego
W tablicach skrótów, które rozwiązują kolizje za pomocą sondowania liniowego, w celu zapewnienia oczekiwanej wydajności , zarówno konieczne, jak i wystarczające jest, aby funkcja skrótu pochodziła z 5-niezależnej rodziny. (Wystarczalność: „Sondowanie liniowe ze stałą niezależnością”, Pagh i in. , Konieczność: „O k-niezależności wymaganej przez sondowanie liniowe i niezależność minutową”, Pătraşcu …
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.