Sparovani dvou mnozin

[Petr Synek]

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 <xmedeko na 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.nikodim na 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
>>
> 
> 
>