jj O(n + n log n) = O(n log n), to plati pro n jdouci k nekonecnu. V
praxi spis plati ze: O(n + n log n) = O(n + n log n) :-)
Petr
Vity Vity wrote:
jen bych ke kolegovi dodal, ze to zavisi na skrytych konstantach, resp. poctu
tech zaznamu ... :-).
-Vity
Dne 21. červenec 2009 14:08 Ondra Medek <xmed...@gmail.com> napsal(a):
No pokud byste mel klasicky List nebo Set, tak nejlepsi je obe mnoziny
seradit - slozitost O(n log n) a pak je projit jednim pruchodem O(n),
tj. celkem O(n + n log n) = O(n log n). Pokud se A a B nemeni prilis,
tak byste mohl vyuzit SortedSet nebo SortedMap, abyste to nemusel po
kazde zmene znovu radit, pak by vas algorimus mel O(n) slozitost, ale
zase insert/delete v seznamech by neco zabral.
Ale vase reseni take neni spatne, za predpokladu, ze se prvky v Map
dobre hashuji, tj. slozitost se pristupu se blizi O(1) a tedy cely
prubeh vaseho algoritmu je pak blizko k O(n).
Jak vidite, pokud si stim chcete hrat, tak si to musite vyzkouset a
zmerit cas :-))
O.
2009/7/21 Michal Nikodím <michal.niko...@asei.cz>:
Mam dve mnoziny A a B. Mnozina A je 100% prvku a v mnozine B je n prvku.
Potrebuju projit mnozinu A a ke kazdemu prvku mnoziny A dohledat
odpovidajici prvek mnoziny B.
Mnoziny jsou plne v moji rezii. Muze to byt List, Map, dle libosti. Prvky
mnozin jsou tez plne v moji rezii a tak jak to mam ted ma kazdy prvek
unikatni atribut ID (Long) a equals a hashcode je napsan pro tento atribut.
Mnozina B je celkem casto prenactena a ja potrebuju po prenacteni proparovat
s mnozinou A.
Vysledkem je mnozina C kde prvkem je objekt ktery obsahuje instanci z
mnoziny A a spravnou instanci z mnoziny B (nebo null).
Jak tohle delat co nejefektivneji ?
Osobne to resim tak, ze mam mnozinu B jako Map<Long, Prvek> pricemz iteruju
mnozinu A a podle ID z mapy dohledam odpovidajici prvek B.
Ale moc se i to nezda.
--
Ondra Medek
