Win a copy of Svelte and Sapper in Action this week in the JavaScript forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Bear Bibeault
• Junilu Lacar
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Henry Wong
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• salvin francis
• Frits Walraven
Bartenders:
• Scott Selikoff
• Piet Souris
• Carey Brown

# efficient algorithm?

Ranch Hand
Posts: 235
hi,
I have two arrays contain a group of integer. I want to find if they have the same groups of number or not, although the order is different. Is there faster algorithm than nested for loops?
Thanks

Ranch Hand
Posts: 1953
1) first thing, compare length, if not equal, gone!
2) make copy of each, O(n )
3) sort both copy, O(n * lg n)
4) compare each pair O(n)
Over all O(n * lg n)
better than nested loop, which is O(n*n)

Roseanne Zhang
Ranch Hand
Posts: 1953
If the n = 13,000,000,000, you will see huge speed difference.

Roseanne Zhang
Ranch Hand
Posts: 1953
Use your calculator to do the comparison calculation, you will get a good understanding of computer algorithms.
Of course, if n = 130, the nested loop algorithm is simple and better. Since the time saving on computing does not worth the programming effort and the overhead of the complicated algorithms.
Thanks!
Roseanne
[This message has been edited by Roseanne Zhang (edited September 08, 2001).]

Simon Xu
Ranch Hand
Posts: 235
Roseanne
But how about not integer value, such as String, Char.
In fact, I have two arrays (or vector) which store two methods' parameters. I would like to compare if these two are the same, although the parameter order could be different.
Simon

Roseanne Zhang
Ranch Hand
Posts: 1953
Define a java.util.Comparator for the object you want to compare, then the algorithm would be the same.
If speed is your major concern, do not use Vector, use array instead, according to some research, Vector is at least 3 times slower than straight array for some obscure reason.
Roseanne

Roseanne Zhang
Ranch Hand
Posts: 1953
Here is an example of how to use Comarator:
http://www.geocities.com/developergrp/presentations/SortBy.htm
[This message has been edited by Roseanne Zhang (edited September 08, 2001).]

Simon Xu
Ranch Hand
Posts: 235

Thank you very much, Roseanne.