Pytania otagowane jako data-structures

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

5
Dla jakiego rodzaju danych są operacje tabeli skrótów O (1)?
Od odpowiedzi do (Kiedy) jest wyszukiwanie tablicy skrótów O (1)? , Rozumiem, że tabele skrótów mają O(1)O(1)O(1)zachowanie w najgorszym przypadku ) , przynajmniej zamortyzowane, gdy dane spełniają określone warunki statystyczne, i istnieją techniki, które pomagają rozszerzyć te warunki. Jednak z perspektywy programisty nie wiem z góry, jakie będą moje dane: …
2
Jaka jest różnica między abstrakcyjnymi a konkretnymi strukturami danych?
Myślałem asocjacyjną (tj mapie lub słownika) i tabela mieszania były takie same pojęcia, dopóki nie zobaczyłem w Wikipedii tym W przypadku słowników z bardzo małą liczbą powiązań sensowne może być zaimplementowanie słownika przy użyciu listy powiązań, połączonej listy powiązań. ... Najczęściej stosowaną implementacją tablicy asocjacyjnej ogólnego przeznaczenia jest tablica skrótów: …
2
Pokoloruj drzewo binarne, aby było czerwono-czarnym drzewem
Częstym pytaniem w rozmowie kwalifikacyjnej jest podanie algorytmu określającego, czy dane drzewo binarne ma zrównoważoną wysokość (definicja drzewa AVL). Zastanawiałem się, czy możemy zrobić coś podobnego z czerwono-czarnymi drzewami. Biorąc pod uwagę dowolne bezbarwne drzewo binarne (z węzłami NULL), czy istnieje „szybki” algorytm, który może określić, czy możemy pokolorować (i …
2
Jak wdrożyć algorytm AO *?
Zauważyłem, że podczas implementacji algorytmów wyszukiwania stosowane są różne struktury danych. Na przykład używamy kolejek do implementacji pierwszego wyszukiwania szerokości, stosów do implementacji wyszukiwania z głębokości pierwszej i stosów min do implementacji algorytmu A * . W takich przypadkach nie musimy jawnie budować drzewa wyszukiwania. Ale nie mogę znaleźć prostej …
2
Udowodnienie, że plik binarny ma
Próbuję udowodnić, że sterty binarne z węzłami mają dokładnie liści, biorąc pod uwagę, że stertę buduje się w następujący sposób:nnn⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceil Każdy nowy węzeł jest wstawiany przez przeskalowanie w górę . Oznacza to, że każdy nowy węzeł musi zostać utworzony przy następnym dostępnym podrzędnym. Rozumiem przez to, że dzieci …
2
Czym jest ta struktura / koncepcja danych, w której wykres punktów definiuje podział na przestrzeń
Zetknąłem się z algorytmem rozwiązywania rzeczywistego problemu i pamiętam klasę, w której wziąłem udział, gdzie zrobiłem coś bardzo podobnego dla niektórych na zadanie domowe. Zasadniczo jest to wykres punktów, a linie są rysowane tak, aby były w równej odległości między dwoma punktami. Tworzy idealną przegrodę, w której linie wokół punktu …
6
Jak zaimplementować dwa stosy w jednej tablicy?
Chciałbym zacząć od stwierdzenia, że ​​to NIE jest zadanie domowe. Czytam Wstęp do algorytmów - słynny tekst CLRS, aby stać się lepszym programistą. Próbuję samodzielnie rozwiązać problemy i ćwiczenia podane w książce. Próbuję rozwiązać Ćwiczenie 10.1-2 z rozdziału 10 Elementarne struktury danych z CLRS wydanie drugie. Oto, co jego stany: …
3
Jak podejść do problemów związanych z dynamicznym wykresem
Zadałem to pytanie przy ogólnym przepełnieniu stosu i skierowano mnie tutaj. Świetnie będzie, jeśli ktoś będzie w stanie wyjaśnić, w jaki sposób ogólnie podejść do częściowych lub w pełni dynamicznych problemów graficznych. Na przykład: Znajdź najkrótszą ścieżkę między dwoma wierzchołkami na niekierowanym wykresie ważonym dla wystąpień, gdy krawędź jest usuwana …
2
Która metoda jest preferowana do przechowywania dużych obiektów geometrycznych w kwadracie?
Podczas umieszczania obiektów geometrycznych w kwadracie (lub oktawie) możesz umieszczać obiekty większe niż pojedynczy węzeł na kilka sposobów: Umieszczenie odniesienia do obiektu w każdym liściu, dla którego jest zawarty Umieszczenie odniesienia do obiektu w najgłębszym węźle, dla którego jest w pełni zawarty Zarówno # 1, jak i # 2 Na …
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …
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.