Hi James, your approach is cool, The bitmap approach works in O(n), but as mention by dave, it take extra memory and initialization.
If we dont want to use extra memory, can it be done in O(n)? Thank You MJ On Nov 21, 8:11 pm, Dave <[EMAIL PROTECTED]> wrote: > 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 -- 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 -~----------~----~----~----~------~----~------~--~---
