Mailing List Archive


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[tlug] array duplicate check [C]



Nguyen Vu Hung writes:

 > whose the complexity is N*M in the worst case. The performance will be
 > a pain if N or M grow big.

You want to ensure the intersection is empty, right?  If at least one
of M and N is small, brute force it.  If they're large, you want a
Bloom filter.  O(N+M) in the average case (which is a minimum for this
problem as you must examine each element of both arrays at least
once).  I don't know offhand how to compute worst case (it might be
O(N*M)), but worst case is incredibly unlikely (and you can adjust
"incredible" to taste).



Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links