develooper Front page | perl.beginners | Postings from February 2009

Re: How to speed up two arrays compare.

Thread Previous | Thread Next
From:
Chas. Owens
Date:
February 11, 2009 13:53
Subject:
Re: How to speed up two arrays compare.
Message ID:
58ce48dc0902111352w46485d00w142909ac2818ac0f@mail.gmail.com
On Wed, Feb 11, 2009 at 11:07, kevin liu <lwtbenben@gmail.com> wrote:
snip
>> 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.
snip

You must have n, there is no other way (which is why even using a hash
version has an amortized cost of O(n)) because you must examine all n
items in the first array.  In the naive case (searching the whole
second array) you multiply n by m because for every item in the first
array you must search m items in the second array.  Changing the naive
case to use a binary search reduces the number of elements in the
second array from m to nl m/nl 2 or as it is normally written log m.
This is because a search through the longest path through the
(balanced) binary tree is log m (so for 128 items the longest path is
7, for 256 it is 8, for 512 it is 9, etc.).


-- 
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About