Chciałbym zaimplementować sobie tablicę asocjacyjną. Czy jest możliwość stworzenia takiej tablicy bez iterowania po całej tablicy kluczy przy odczytywaniu wartości o danym indeksie-kluczu? A może jest jakiś sposób na zoptymalizowanie takiej iteracji? Bo przejeżdżanie za każdym razem po całej tablicy za bardzo zwiększy złożoność mojego kodu, a potrzebuję czegoś co działa szybko.
0
0
Musisz to implementować samemu? Takie rzeczy są w bibliotece standardowej: chociażby std::map i std::unordered_map. (Szukaj pod Associative containers)
1
Metod jest kilka:
#sortujesz klucze a potem robisz binarny search (przeszukiwanie ma złożonośc o(ln n))
#budujesz drzewo binarne
#liczysz hash dla klucza, odnajdujesz i na podstawie hasha, gdzie masz zacząć poszukiwania (najszybsze ale najwięcej kodu do napisania).
0
@Hysterus zbalansowane drzewa binarne mają O(log(n)) czasu szukania klucza, hashmapa daje O(1)
0
Teoretycznie mogę skorzystać, lecz jest to zadanie na studia i na kolejny etap będę musiał i tak użyć tylko własnych struktur danych.
Kurcze, wyczytałem tam, że klasa "map" przy szukaniu ma złożoność logarytmiczną. Przy iterowaniu całej tablicy złożoność jest n, jak to uzyskali? :P
0
Oj, zacząłem odpisywać i zanim odpisałem pojawiły się dwa posty :)
Dzięki za podpowiedź, spróbuję w takim razie coś wykombinować :)
0
Hysterus napisał(a):
Kurcze, wyczytałem tam, że klasa "map" przy szukaniu ma złożoność logarytmiczną. Przy iterowaniu całej tablicy złożoność jest n, jak to uzyskali?
To się jeszcze bardziej zdziwisz - nawet stos i lista przy iterowaniu całości złożoność jest n!