用莫顿序对BH算法的改进

详细分析Barnes-Hut算法的基本原理,介绍BH空间的分割和BH树的创建,并用伪码方式描述了BH算法,同时介绍了Z序的生成方法.利用莫顿映射得到粒子的键值对粒子进行排序,由于N-Body仿真粒子的位移很小,有序的粒子经过一步仿真后基本保持有序.因为对有序粒子的排序和用有序粒子来建BH树的时间复杂度都为O(n),文章提出了对BH算法进行改进的一种方法,使得其时间复杂度从O(nlogn)降为O(n)。

The Improvement on BH Algorithm Using Morton-order

The keystone of BH algorithm,the division of BH space and the process of building BH tree are detailed.The theory and the generation method of Z-order are also introduced.The particles are sorted by using their key values that can be got from Morton-mapping.In the N-body simulation,the displacements of particles are very small,so after one simulation step,the particles are almost kept sorted.Because the time complexity of the process of sorting almost sorted particles and building a tree using sorted particles is O(n),it presents a method to improve the Barnes-Hut algorithm,which decreases the time complexity from O(nlogn) to O(n).