Ovidiu.Silaghi wrote: > I have two arrays of strings (lets say 10000 elements) and I need to > compare them to see if they have the same elements. > The arrays have only UNIQUE values and the same dimension! Arrays are > not sorted.. > (Language VB6/VBA with Excel) > I want two know which is the fastest/better solution... > > Thanks in advance, > Ov
As has been pointed out, this problem is Omega(mn) where m is string length and n is the array size. The lower bound is because in general you need to inspect every character at least once and the upper bound results from a hash table that (with probability approaching 1) allows comparison with no _more_ than mn examinations of each character. You can do better on average if you know something about the strings and if the arrays are likely to be different much of the time. For example there are many ways to say the two arrays are _different_ in O(n) rather than O(mn). For example if your strings include an explicit length field, you can compute a length histogram in O(n). You can compute histograms for character frequency of say first, last, and middle characters and compare those. Yada yada... --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
