Re: [OT] Hints for an algorithm - avoiding O(n^2)

[Jano <nono@unizar.es>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 828 bytes --]

Jean-Pierre Rosen dice...
> 
> "Jano" <402450@cepsz.unizar.es> a �crit dans le message de news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
> > The problem is a simple one: I'm planning to write a simulator of
> > sideral-like objects using the Newton laws (precision is not a top
> > priority). The obvious way is to compute the force interactions
> > between each pair of objects, sum them all, and iterate over... but
> > this is O(n^2). To be precise, there are n(n-1)/2 forces to be
> > computed if I'm right (n the number of objects).
> >
> If I remember my Newton laws correctly, you just need to compute the force between an object and the center of mass of all other
> objects.

I discussed this too with a colleague, but it's equivalent (apart from 
the subtleties noted by other posters) in computing time.