On Wed, Feb 11, 2009 at 11:22 PM, John W. Krahn <[email protected]> wrote:
> kevin liu wrote:
>
>> Hi everybody:
>>
>
> Hello,
>
>
> I have two arrays(@nwarray0 and @nwarray1) in my program and i want
>> to make sure that
>> all the elements in @nwarray0 could be found in @nwarray1.
>> Here is my implementation:
>> -------------------------------------------------------
>> foreach my $srctemp ( @nwarray0 ) {
>>
>> foreach my $tgttemp ( @nwarray1 ) {
>> if ( $tgttemp eq $srctemp ) {
>> $found = 1;
>> last;
>> }
>> }
>> if ( $found == 1 ) {
>> $found = 0;
>> next;
>> }
>> else {
>> return 1;
>> }
>> }
>> --------------------------------------------------------
>> But this algorithm takes a long time to compare, could you please
>> help to improve this piece of
>> code to less the time needed?
>>
>
> 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.
>
>
> If the elements of @nwarray1 were in a hash then you could reduce your
> worst case to O( n ).
>
