Hey, As Bala suggested, at the simplest solution complexity seems to be O(n^2), I don't understand how is any other solution described here is better then O(n^2)!
Regards On 5/22/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > > yes, you are right. > > On 5月21日, 下午1时56分, Ray <[EMAIL PROTECTED]> wrote: > > Hi WangLei, > > > > The approach you provide is to compute the angle of every point > > pair<pi, pj>, i != j. > > e.g. the angles are stored in an array. And then find the maxium > > identical elements > > of the array. So it's converted to find the Multitude Number: > > 1. Sort the array > > 2. traverse the array > > It runs O(nlogn + n). > > So the whole time complexity is O(n^2*lgn). Is that true? > > > > Thanks! > > > > On May 15, 2:43 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > > > > > > > > > for every point Pi, we compute the angle of the line which connects Pi > > > and other point Pj, and sort all Pj-s by the angle and then let j from > > > i to n and j!=i, finding the max collinear point set that includes Pi. > > > the complexity of this process is O(n*ln(n)+n).Let i=1 to n ,so the > > > complexity of the whole problem is O(n^2*ln(n)) . > > > > > On 5月14日, 下午10时06分, Balachander <[EMAIL PROTECTED]> wrote: > > > > > > Hey.. > > > > > > How can reduce the Comp from O(n) to O(log n) > > > > How are arranging the lines [ nC2 lines] > > > > for the purpose of finding the max no of collinear points > > > > > > For finding all lines O(n^2) > > > > For Checking the presence ..O(n) > > > > > > Pls reply ,,How can u reduce the comp to Log n. > > > > > > Bala > > > > > > On May 14, 6:57 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> > wrote: > > > > > > > I have a brute force solution with the time complexity of > > > > > O(n^2ln(n))... > > > > > how can we impove it? > > > > > On 5月14日, 下午6时50分, PopUp <[EMAIL PROTECTED]> wrote: > > > > > > > > I have brute force solution, this was asked in Google Interview. > > > > > > > > On May 14, 1:36 pm, "Cool Guy" <[EMAIL PROTECTED]> wrote: > > > > > > > > > I think that this problem is similar to cryptology. > > > > > > > (Cryptology is method for one solution when exists a lot of > numbers, but > > > > > > > reverly think, I think that max collinear points will be find) > > > > > > > > > Actually, I don't have any idea. :) > > > > > > > > > Can you any idea for resolving this problem? > > > > > > > > > 2007/5/14, PopUp <[EMAIL PROTECTED]>: > > > > > > > > > > HI, > > > > > > > > Great group!! > > > > > > > > I have a problem, some of you might have heard about that. > We have set > > > > > > > > of n points in space. Now we have to find a set(with the max > elements) > > > > > > > > of collinear points or we can say find the max collinear > points. > > > > > > > > > > Thanks, > > > > > > > > Popup- 隐藏被引用文字 - > > > > > > > > - 显示引用的文字 -- 隐藏被引用文字 - > > > > > > - 显示引用的文字 -- 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 -~----------~----~----~----~------~----~------~--~---
