Я пишу статью о проблеме n-body, и я хотел бы быть технически точным.
Код здесь . А вот и комментарии и циклы:
/**
* 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). </p>
По процесс исключения , который оставляет O (n log n) в качестве другого варианта.
Глядя на сетку, я думаю, O (1/2 n ^ 2) = O (n ^ 2)
Глядя на циклы, я думаю, что внутренний цикл равен < n, но я не уверен, что он полностью соответствует log n.
Если я перебираю n, чтовыглядит добавление внутреннего цикла log n? Если не внутренний цикл, внешний цикл?