在不到O(n^2)的时间内模拟多个物体之间的重力
在不到O(n^2)的时间内模拟多个物体之间的重力
提问于 2017-06-29 05:12:56
我正在写一个n粒子的模拟，这些粒子都是相互“引力”吸引的。为了计算每个粒子上的力，我迭代遍历粒子列表。对于列表中的每个粒子，我迭代相同的列表，计算每个其他粒子由于重力而产生的加速度，并将每个加速度添加到该粒子上的净力。
虽然此算法有效且或多或少准确，但它的执行时间为O(n^2)。有没有更快的算法？
回答 1
Stack Overflow用户
发布于 2017-06-30 21:47:21
对于非常高的N值，通过创建网格，然后为该网格上的每个点计算所有粒子施加的平均重力，可以更快地近似n体重力。然后，您可以查看每个粒子最近的几个网格点，并从这些网格点近似粒子上的总引力。但是，只有当网格上的总点数小于粒子数时，这才会更快。
其他一些方法是Barnes-Hut模拟和快速多极子方法，但随着时间的推移，这些方法会累积误差。
然而，根据模拟的长度，你无论如何都会开始积累误差，因为计算机中(几乎)所有的非整数都是近似值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44812631
复制相关文章
相似问题
腾讯云开发者
