这个n体问题是O(n ^ 2)还是O(n log n)? [英] Is this n-body problem O(n^2) or O(n log n)?

问题描述

我正在写一篇有关n体问题的文章，并且我希望在技术上是准确的.

代码为

I'm writing an article on the n-body problem, and I'd like to be technically accurate.

The code is here. And here are the comments and loops:

/**
 * Given N bodies with mass, in a 3d space, calculate the forces of gravity to be applied to each body.  
 * 
 * This function is exported to JavaScript, so only takes/returns numbers and arrays.
 * For N bodies, pass and array of 4N values (x,y,z,mass) and expect a 3N array of forces (x,y,z)
 * Those forcess can be applied to the bodies mass to update the its position in the simulation.
 * Calculate the 3-vector each unique pair of bodies applies to each other.
 * 
 *   0 1 2 3 4 5
 * 0   x x x x x
 * 1     x x x x
 * 2       x x x
 * 3         x x
 * 4           x
 * 5
 * 
 * Sum those forces together into an array of 3-vector x,y,z forces
 * 
 * Return 0 on success
 */

 // For all bodies:

  for (let i: i32 = 0; i < numBodies; i++) {                   // TypeScript.  i32 is type 32bit int
    // Given body i: pair with every body[j] where j > i
    for (let j: i32 = i + 1; j < numBodies; j++) {             // is this "n" or "log n"?
      // Calculate the force the bodies apply to one another
      stuff = stuff
    }
  }
  return stuff

I'm fairly certain the algorithm is > O(n) and <= O(n*n).

By process of elimination that leaves O(n log n) as the other option.

Looking at the grid, I think O(1/2 n^2) = O(n^2)

Looking at the loops, I think the inner loop is < n, but I'm not sure if it's all the way to log n.

If I'm looping through n, what does adding a log n inner loop look like? If not an inner loop, an outer loop?

解决方案

Assuming that Calculate the force the bodies apply to one another is an O(1) operation then what you have is the following summation.

这篇关于这个n体问题是O(n ^ 2)还是O(n log n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！