> Which is the fastest solution for comparing two arrays?
Random guess.
Or, if it takes too much time to call random number generator, you can
simply return "non-equal" without any checks whatsoever. I doubt it can
get any faster than that.
--~--~-~--~~~---~--~~
Thanks guys for your help!
Kind regards,
O
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, se
Ovidiu.Silaghi wrote:
> I have two arrays of strings (lets say 1 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 f
careful, things don't collapse so easily; otherwise we'd always have
either O(n) or O(1).
Agreed, it is a constant, as much as traversing a bst is a constant
bound above by some fixed value. When determining runtime in big-O, you
must always use the upper bound.
Now for strings, m would be some
Hi L7,
so what is m - it is a constant isnt't it.
So O(k*n) = O(n)
which is different from O( n log n) .
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to
Hi Amal,
Unless one needs to compare array A with many arrays(in this example it
is just one), it is not a good idea to spend on constructing aTRIE for
A...do you agree?
Siva
Amal wrote:
> Hey Guys ,
> I think using a Data structure like TRIE could also be Good solution for
> the question .
>
Hi
I havent used B-tree at all...but all i wanted to say was to use a
height balanced BST so that the worst case height is O(logn)since
B-tree is one of these, thought it cud be used...
Siva
ridvansg wrote:
> L7,
> from the first array make a hash table H-> O(n)
>
> go through the second ar
Since each array has only UNIQUE values, hashing may achieve better
performance.
The problem is finding a good hash function which is both fast and
collision-free.
Collision-free means the following iteration and search in another
array can be as fast as possible.
Ovidiu.Silaghi wrote:
> The arra
Hey Guys ,
I think using a Data structure like TRIE could also be Good solution for the question .
Just put the strings of one array into a TRIE and then search for the strings of the other array.
The Order will be 2 * O(n * d) approx
where d is the average length of all the strings in an arra
To sort an array A you could use Radix Sort, which complexity is O(d*n), where d = log2(max(A)). So,sort the first array -> O(d*n)sort the second array -> O(e*n)compare the two arrays -> O(n)the solution : (d+e+1)*O(n) = O(n)
Use it only if (d+e+1) is smaller than the hash constant.Bruno Avila2006/
You are ignoring the complexity of the comparison function (reqd. for
sorting). It is not O(1) for string comparison. It will be a
function of the input size too.
On 7/19/06, L7 <[EMAIL PROTECTED]> wrote:
>
> @ridvansg
>
> Like I mentioned, O(n) for creating a hash table *ignores* the hash
> fu
@ridvansg
Like I mentioned, O(n) for creating a hash table *ignores* the hash
function itself, which, for strings is going to be at least O(m).
So now you have O(n*m)
O(n*m) + O(n) (with the compare)
So, unless O(m*n) < O(n log n), two sorts and compare will do the trick
without any extra space
L7,
from the first array make a hash table H-> O(n)
go through the second array and test if the element is present in H1
->O(n)
so the solution is 2*O(n)=O(n)
Your solution:
sort the first array -> O(n log n)
sort the second array -> O( n log n)
compare the two arrays -> O(n)
the solution :
How does a hash table (or B-tree) determine if the two arrays are the
same?
A Hash table is hardly O(n) unless you do not hash the strings.
After designing these two structures (for each array) you still have to
compare the two to see if they are equal (which if it turns out they
are _always_ tak
Using Hash table gives the best performance in terms of time
complexity. I n is the number of strings in each array, it is O(n).
But if space is at a premium, use B-trees and the complexity would be
O(nlogn).
Bye,
Siva
Ovidiu.Silaghi wrote:
> I have two arrays of strings (lets say 1 element
15 matches
Mail list logo
