Front page | perl.beginners |
Postings from February 2009
kevin liu wrote:
> On Wed, Feb 11, 2009 at 11:22 PM, John W. Krahn <jwkrahn@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
Thread Previous
|
Thread Next