直接数值模拟(DNS)和粒子搜索

直接数值模拟

网格法避免DNS方法的原因，DNS要求的网格数较大，计算量、存储量大。

采用先验的湍流模型，可以减轻求解NS方程的负担。

让我好奇的是，SPH方法中，很多学者往往采用DNS方法分析和实现NS方程的求解。

不过从理论发展阶段上看，一般是先有较为成熟、健壮的DNS实现，才会考虑一些可能的先验模型方案来加速计算。

关于湍流模型在SPH方法上的应用，还需要进一步的学习考究。

湍流模型是考虑DNS计算所需网格量过大而引入。从减低计算复杂度的角度上，NNPS是SPH法中最耗时的部分，所以我想到介绍NNPS。

在粒子的相互作用中涉及到两种技术：1. 最近相邻粒子搜索法(NNPS)；2. 粒子对的相互作用。

不仅要算的对，还需要算的快，还要存储少！

在《光滑粒子流体动力学--一种无网格方法》中，介绍了三种最近相邻粒子搜索(NNPS)算法：

简单而直接，每次搜索都遍历所有粒子。显然，它的时间复杂度是$o(N^2)$。它不适宜计算粒子数量庞大的问题，只有在粒子数量较少的情况下才可能被使用。

当粒子近似的光滑长度为空间常量的情况下，链表搜索法是有效的。在实现链表算法时，在问题域内铺设临时网格。如果临时网格单元内的平均粒子数量足够小，则链表搜索法的时间复杂度是$o(N)$。

树形搜索法非常适合求解具有可变光滑长度的问题，这种算法通过粒子的位置来构造有序树（二叉树、四叉树、八叉树）。树形搜索算法的时间复杂度是$o(N\lg{N})$。

在实际编程实现中，往往可以采用面向对象方法、递归函数等编程手段实现树形搜索法，经有关资料证明，结合树形搜索法的SPH实现是非常高效和健壮的，尤其是用于求解具有可变光滑长度和粒子数量庞大的问题时。

SPlisHPlasH是一个使用C++语言编写的SPH实现。

以上只是针对时间复杂度的说明，考虑空间复杂度，则对应考虑数据存储的空间。

老师让我把全班60本作业本按封面上的学号排好。

于是我灵活运用了快速排序的知识，从本堆中随便抽出一本，把学号比它小的本子放在左边，学号比它大的本子放在右边，再从左边这一堆挑出一本……

如此一来我的排本子的时间复杂度就从普通人用的插入排序的$o(N^2)$变成了$o(N\lg{N})$。周围的同学投来好奇的目光，我洋洋自得，心想学过算法的我就是不一样。

快速排序效率果然很高，不一会儿，

我的桌子就放不下了_(:з」∠)_

(评论：忽略系数和空间复杂度的后果。)

粒子数量巨大的时候，如何处理效率问题（计算效率、数据存储和交互）？应该还是从原理上来处理：光滑粒子。