我正在用 n 个粒子编写一个模拟，这些粒子都“在引力上”相互吸引。为了计算每个粒子上的力，我遍历了一个粒子列表。对于列表中的每个粒子，我遍历同一个列表，计算由于每个其他粒子引起的重力加速度，并将每个加速度添加到该粒子上的净力。
虽然此算法有效并且或多或少准确，但它的执行时间为 O(n^2)。是否存在更快的算法？
最佳答案
对于非常多的 N，通过创建网格来近似 n 体引力可能会更快，然后为该网格上的每个点计算所有粒子施加的平均引力。然后，您可以针对每个粒子查看最近的几个网格点，并从中估算粒子上的总引力。但是，如果网格上的总点数小于粒子数，这只会更快。
其他一些方法是 Barnes–Hut 模拟和快速多极方法，但这些方法会随着时间累积误差。
但是，根据模拟的时间长短，您无论如何都会开始累积误差，因为(几乎)计算机中的所有非整数都是近似值。
关于algorithm - 在不到 O(n^2) 的时间内模拟许多物体之间的重力，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44812631/