Informatyka search-trees

1

Dowód złożoności czasu dla implementacji problemu segmentu dystansowego w drzewie segmentów

Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy ZAAA. I to można zrobić wO (logn )O(log⁡n)\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(log⁡n)\mathcal{O}(\log n). Ten link (i wiele innych) mówi, że możemy udowodnić, że …

10 data-structures runtime-analysis search-trees intervals

1

Aktualizacja zakresu + zapytanie o zakres z binarnie indeksowanymi drzewami

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/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http : //apps.topcoder.com/forums/? module = Thread & ThreadID = 756271 & start = 0 & mc = 4 # 1579597 Ale nawet po przeczytaniu …

10 data-structures binary-trees search-trees

2

Czy przydatne są probabilistyczne struktury danych wyszukiwania?

SkipList zapewnia to samo O(logn)O(log⁡n)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 jest wystarczająco „zrównoważona”. W szczególności z prawdopodobieństwem1/nc1/nc1/n^c dla jakiejś stałej c>0c>0c>0, zrównoważona …

9 data-structures search-trees probabilistic-algorithms

3

Logarytmiczna vs podwójna logarytmiczna złożoność czasu

Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?O (log( log( n ) )O(log⁡(log⁡(n))\mathcal{O}(\log(\log(n))O (log( n ) )O(log⁡(n))\mathcal{O}(\log(n)) Dzieje się tak, gdy na przykład używa się drzew van Emde Boasa zamiast bardziej tradycyjnych implementacji drzewa wyszukiwania binarnego. Ale na przykład, jeśli weźmiemy to w najlepszym przypadku …

9 algorithms complexity-theory binary-trees algorithm-analysis search-trees

Pytania otagowane jako search-trees