Pytania otagowane jako data-structures

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

1
Czy istnieje istniejąca struktura danych o ustalonym rozmiarze, która wypchnie najstarszy / ostatni element, jeśli wstawiony zostanie nowy element?
Szukam struktury danych, która wypchnie jej najstarszy / ostatni element, jeśli wstawiony zostanie nowy element. Na przykład niech Dreprezentuje strukturę. Dzawiera 3 elementy Number Dwartości domyślnych tego typu będą inicjowane do 1, 2i 3. D=[1,2,3]D=[1,2,3]D = [1, 2, 3] Jeśli Numberto zawiera wartość 5jest włożona D, 3zostanie wypchnięty, natomiast 1i …
1
Problemy, dla których algorytmy oparte na zawężaniu partycji działają szybciej niż w czasie logarytmicznym
Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą udoskonalenia partycji innych niż te wymienione na stronie Wikipedii. Spośród …
1
Obsługa struktur danych dla lokalnego wyszukiwania SAT
WalkSAT i GSAT są dobrze znanymi i prostymi lokalnymi algorytmami wyszukiwania służącymi do rozwiązania logicznego problemu satysfakcji. Pseudokod algorytmu GSAT jest kopiowany z pytania Implementacja algorytmu GSAT - Jak wybrać literał, który ma być odwrócony? i przedstawione poniżej. procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do …
5
Skuteczna kompresja nieoznakowanych drzew
Rozważ nieoznakowane, ukorzenione drzewa binarne. Możemy skompresować takich drzew: gdy istnieją wskaźniki do poddrzew i T ' z T = T ' (ustne = jak równość strukturalne), możemy zapisać (wlog) T i zastąpić wszystkie wskaźniki do T ' z wskazówki dla T . Zobacz odpowiedź uli na przykład.T.TTT.′T′T'T.= T′T=T′T = …
2
Czy drzewa cięte łączem są kiedykolwiek wykorzystywane w praktyce do obliczeń maksymalnego przepływu lub innych zastosowań?
Wiele algorytmów maksymalnego przepływu, które zwykle widzę zaimplementowanych, algorytm Dinica, push push i inne, mogą mieć asymptotyczny koszt czasu ulepszony dzięki zastosowaniu dynamicznych drzew (znanych również jako drzewa cięte łączem). Wciśnij etykietę w trybie lub O ( V 3 ) lub O ( V 2 √)O ( V2)mi)O(V.2)mi)O(V^2E)O ( V3))O(V.3))O(V^3)normalnie, …
1
Dlaczego programowanie funkcjonalne nie badało dynamicznych drzew?
Drzewa dynamiczne odgrywają ważną rolę w rozwiązywaniu problemów, takich jak przepływy sieciowe, wykresy dynamiczne, problemy kombinatoryczne („Drzewa dynamiczne w praktyce” Tarjana i Wernecka) oraz ostatnio łączone słowniki („Prosty słownik łączący” Adama Karczmarza), Przez drzewa dynamiczne odwołuję się do definicji podanej w dokumencie Sleator & Tarjan zatytułowanym „Struktura danych dla drzew …
12
Struktura danych lub algorytm do szybkiego znajdowania różnic między łańcuchami
Mam tablicę 100 000 ciągów o długości . Chcę porównać każdy ciąg z każdym innym, aby zobaczyć, czy dwa ciągi różnią się o 1 znak. W tej chwili, gdy dodam każdy ciąg do tablicy, sprawdzam go względem każdego łańcucha już w tablicy, który ma złożoność czasową .kkkn(n−1)2kn(n−1)2k\frac{n(n-1)}{2} k Czy istnieje …
1
Jakie klasy struktur danych można utrwalić?
Trwałe struktury danych to niezmienne struktury danych. Operacje na nich zwracają nową „kopię” struktury danych, ale zmienioną przez operację; stara struktura danych pozostaje jednak niezmieniona. Wydajność jest na ogół osiągana przez dzielenie się niektórymi danymi bazowymi i unikanie pełnego kopiowania struktury danych. Pytania: Czy istnieją wyniki dotyczące klas struktur danych, …
1
Jak czas działania algorytmu Ukkonen zależy od wielkości alfabetu?
Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?). Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1): „... wszystkie algorytmy Aho-Corasick, Weiner, Ukkonen i McCreight wymagają albo przestrzeni , albo ograniczenie czasowe …
1
Ważona suma ostatnich N liczb
Załóżmy, że otrzymujemy liczby w strumieniu. Po otrzymaniu każdej liczby należy obliczyć ważoną sumę ostatnich liczb, przy czym wagi są zawsze takie same, ale dowolne.NNN Jak skutecznie można to zrobić, jeśli pozwolimy zachować strukturę danych, która pomoże w obliczeniach? Czy możemy zrobić coś lepszego niż , tj. Przeliczać sumę za …
1
Zapisywanie przy inicjalizacji tablicy
Niedawno przeczytałem, że można mieć tablice, które nie muszą być inicjowane, tzn. Można z nich korzystać bez konieczności poświęcania czasu na ustawianie wartości domyślnej dla każdego elementu. tzn. możesz zacząć używać tablicy tak, jakby została ona zainicjowana wartością domyślną, bez konieczności jej inicjowania. (Przepraszam, nie pamiętam, gdzie to przeczytałem). Na …
2
Wydajne algorytmy dla problemu widoczności pionowej
Myśląc o jednym problemie, zdałem sobie sprawę, że muszę stworzyć wydajny algorytm rozwiązujący następujące zadanie: Problem: otrzymujemy dwuwymiarowe kwadratowe pudełko o boku nnn którego boki są równoległe do osi. Możemy spojrzeć na to z góry. Istnieją jednak również mmm segmenty poziome. Każdy segment ma całkowitą współrzędną yyy ( 0≤y≤n0≤y≤n0 \le …
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.