algorithm - 这个 n 体问题是 O(n^2) 还是 O(n log n)？

Question

我正在写一篇关于 n 体问题的文章，我希望在技术上准确。

代码在这里。以下是评论和循环：

/**
 * 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

我相当确定算法是 > O(n) 和 <= O(n*n)。

通过排除过程留下 O(n log n) 作为另一个选项。

看网格，我认为 O(1/2 n^2) = O(n^2)

查看循环，我认为内部循环是< n，但我不确定它是否一直到log n.

如果我循环通过 n，添加log n内部循环是什么样的？如果不是内循环，是外循环？

标签： algorithmbig-ocomplexity-theory

Answer 1

假设这Calculate the force the bodies apply to one another是一个 O(1) 操作，那么你所拥有的是以下总和。