kevin liu wrote:
On Wed, Feb 11, 2009 at 11:22 PM, John W. Krahn <jwkr...@shaw.ca> wrote:The best you can do with two arrays is exit as soon as an element of @nwarray0 is not found in @nwarray1: my $found = 1; SEARCH: foreach my $srctemp ( @nwarray0 ) { foreach my $tgttemp ( @nwarray1 ) { if ( $tgttemp ne $srctemp ) { $found = 0; last SEARCH; } } } But this will still take O( n * m ) if all the elements of @nwarray0 are in @nwarray1. If the elements of @nwarray1 are sorted then you could a binary search on it and reduce your worst case to O( n * log m ).But how could this be, I have got the best algorithm from Rob, but I don't know why a binary search would be O( n * logm ) Could you please help to explain? Thank you in advance.
The algorithm Rob gave you is O( n + m ) which is usually better than O( n * log m ) for the worst case.
An explanation of binary search can be found at: http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary or: http://en.wikipedia.org/wiki/Binary_search
If the elements of @nwarray1 were in a hash then you could reduce your worst case to O( n ).
As to whether the algorithm Rob presented is the "best" algorithm, that depends on the data being used and how often this operation needs to be preformed.
For example, the algorithm I presented above has a best case of O( 1 ) while the one Rob presented has a best case of O( n + m ).
John -- Those people who think they know everything are a great annoyance to those of us who do. -- Isaac Asimov -- To unsubscribe, e-mail: beginners-unsubscr...@perl.org For additional commands, e-mail: beginners-h...@perl.org http://learn.perl.org/
