Okay. This works better. It is O(n), but also requires a large amount
of extra memory ( regard 512MB to be large), with a corresponding huge
constant overhead to initialize the bitmap. Can you estimate, using
reasonable assumptions, the n for which the O(n log n) algorithm using
sorting would be faster than this algorithm. I think you will find the
breakeven point to be pretty large, perhaps 2^20 or more. So, for n =
10, 100, or 1000, the bitmap as you describe it would be pretty
impractical.
This raises the interesting question: How do you trade off lower
asymptotic order with possible higher cost for smaller values of n.
There are some places where this tradeoff is crucial to program
performance. For example, in manipulating sparse matrices, a common
operation is as follows:
for i = 1 to n
y[index[i]] = a * x[i] + y[index[i]];
You can write code to be fast for large n, but it is more important to
be fast for small n because most of the time n will be small.
Dave
On Nov 20, 7:30 pm, "James Fang" <[EMAIL PROTECTED]> wrote:
> Oh sorry I've made a mistake in the pseudo code:
>
> It should be rectified like this:
> for i=0 to N
>
> > pair = X - array[i];
> > if( bitmap[pair] == marked )
> > found the answer!
> > else
> > mark bitmap[array[i]]
>
> For a 32bit processor , the bitmap takes about 512MB of memory. However, if
> this operation is in server side and is the bottle neck , the bitmap method
> can be tried.
>
> If the integer in the array have a stricted range, like [-x,y], the bitmap
> method can be better applied.
>
> Best Regards,
> James Fang
>
> -----邮件原件-----
> 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
> Dave
> 发送时间: 2007年11月21日 星期三 2:29
> 收件人: Algorithm Geeks
> 主题: [algogeeks] Re: Array of integers
>
> Want to try again?
> Consider the case where array = {2,3} and X = 5.
> First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so
> you mark bitmap[3].
> Then you have pair = 5 - 3 = 2 and noet that bitmap[2] != marked, so
> you mark bitmap[2].
> Presumably, at this point, since you have exhausted array, you deduce
> that there is no solution.
>
> You might also want to talk about the size of bitmap.
>
> Dave
>
> On Nov 20, 11:03 am, James Fang <[EMAIL PROTECTED]> wrote:
>
>
>
> > You can acheive O(n) by using a bitmap.
>
> > the pseudo code can be described below:
>
> > for i=0 to N
> > pair = X - array[i];
> > if( bitmap[pair] == marked )
> > found the answer!
> > else
> > mark bitmap[pair]
>
> > the bitmap can be an array in the RAM or external disk, with each bit
> > represents an integar number.
>
> > Best Regards,
> > James Fang
>
> > On 11月18日, 上午4时42分, geekko <[EMAIL PROTECTED]> wrote:
>
> > > Suppose that you have an array of integers. Given a number X are there
> > > any two numbers in the array in which their summation is equal to the
> > > X? Can you find a solution in O(n)?- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
