6 ms·
The attraction and collision demos are both doing collision detection, which means N! calculations (for each particle check the location of all the other partic
by TheBurningOr 15y ago
The attraction and collision demos are both doing collision detection, which means N! calculations (for each particle check the location of all the other particles that have not been checked relative to this one). Whereas the chain, cloth and I can't recall the name of the third one, are on the order of N calculations (constant interaction with only a fixed number of other particles).
- HardyLeung 15y agoYou mean N^2, not N!
- nlogn 15y agoHe's right actually if the code is written sensibly. Well it should really be (N-1)! but close enough. Think about it in terms of 3 balls. I check ball1 against ball2 and ball3 then move to ball2. It gains me nothing to re-check ball2 against ball1 so I just check it against ball3. When I reach ball3, I have already checked everything and I'm done. The loop should look like this: for (i = 0; i < n; ++i) for (j = i + 1; j < n; ++j)
- dmvaldman 15y agoThat's N*(N+1)/2 steps, or order N^2. Best to visualize as the number of entries on the upper triangle of an NxN matrix.
- HardyLeung 15y agoI think you need to revisit your understand of complexity. It is O(N^2). If you want the exact count, it is N(N-1)/2. N! is an exceedingly large number even for very small N.
- nlogn 15y agoYep I'm wrong. Mixed up factorial just like mistercow said. Thanks for the corrections. And here I was worrying that someone would complain that my loop wouldn't address the issues of collision response necessitating more checks, thus making a recursive solution necessary.
- mistercow 15y agoThat's not N! . N! is (N)(N-1)(N-2)... What you have there is (N)+(N-1)+(N-2)..., which is O(N²)
- deleted 15y ago[deleted]
- mistercow 15y agoIt should be very easy to implement geometric hashing in CoffeeScript, which can greatly improve collision performance.