粒子仅 64 个，Barnes-Hut 就比朴素 O(n²) 慢 1.75 倍：O(n log n) 一定更快这条共识的实测复盘

你写了一个浏览器里的引力 N 体动画粒子 64 个。同事说「朴素 O(n²) 跑不动上 Barnes-Hut 啊那是 O(n log n)」。你照做了结果每帧反而比原来的双重循环慢了 75%。这不是玄学——是我用 Node 22 在同一台机器上、同一份随机初始条件下跑出来的真实数字。背景为什么 N 体动画里这条「共识」会害你N 体问题说的是给 N 个质点两两之间按牛顿引力互相作用每帧重算一次受力再积分位置。浏览器里凡是「粒子相互吸引」的效果——星团坍缩、双星系碰撞、flocking 的引力版、甚至某些流体 SPH 的近邻求和——底层都是它。朴素做法是双重循环对第 i 个质点遍历其余 N-1 个累加引力。复杂度 O(n²)。教科书和不少博客给的建议是「几百个粒子以内朴素法就行Barnes-Hut 在几千粒子才划算。」于是开发者形成了一种肌肉记忆——只要不是 tiny就默认上树。问题出在「默认」二字。O(n log n) 描述的是渐进复杂度它不保证在任何 N 上都比 O(n²) 快。常数因子才是小 N 时的真正裁判。我决定不靠直觉而是把两套实现都写出来、在同一份数据上掐表。解剖朴素 O(n²) 与 Barnes-Hut 到底差在哪朴素法没有任何预处理每帧就是一组嵌套循环// 朴素 O(n²)对第 i 个质点遍历其余所有 j for (let i 0; i N; i) { let fx 0, fy 0; for (let j 0; j N; j) { if (j i) continue; const dx X[j] - X[i], dy Y[j] - Y[i]; const r2 dx * dx dy * dy EPS2; // 软化避免 r→0 时力爆炸 const inv (G * M[i] * M[j]) / (r2 * Math.sqrt(r2)); fx inv * dx; fy inv * dy; } AX[i] fx; AY[i] fy; }Barnes-Hut 的思路是「远处一群点 ≈ 它们质心处的一个点」。它每帧先建一棵四叉树3D 用八叉树把空间递归二分每个内部节点存「总质量 质心」。求第 i 个点的受力时沿树下降若某个节点「宽度 s / 到质心距离 d θ精度阈值常取 0.5~1.0」就整节点当单点近似否则继续下钻。θ 越小越准、越慢。图1四叉树把空间递归二分密处网格更细。每个内部节点聚合子节点总质量与质心对远处节点用单点近似省掉大量两两计算——代价是每帧要重建这棵树本身。关键差异一眼可见朴素法零预处理、零分配Barnes-Hut 每帧要建树、算质心、下钻遍历。后者省下的是「力计算次数」付出的却是「每帧固定的结构开销」。当 N 小到力计算本身就不多时省下的还不够填开销的坑。实证一次真实基准crossover 落在 170 粒子附近我用种子化随机mulberry32seed20260818生成均匀分布的质点固定软化 ε²1、θ0.7在 Node 22 上对每个 N 跑 5 轮取中位数每步耗时仅计时受力计算含建树。朴素法测到 8000Barnes-Hut 测到 64000N粒子数朴素 O(n²) ms/步Barnes-Hut ms/步BH 相对朴素320.00250.0185慢 7.46×640.00910.0160慢 1.75×1280.03680.0411慢 1.11×1920.08350.0735快 1.14×2560.15340.1169快 1.31×5000.58030.4343快 1.34×10002.32251.2396快 1.87×20009.36342.9889快 3.13×400038.58287.5689快 5.10×8000153.646316.0636快 9.57×16000≈614*39.1921快 ≈15.7×64000≈9830*342.3924快 ≈28.7×带 * 为按 N² 外推仅作量级参考非实测点。图2双对数坐标下朴素法是一条斜率 2 的直线每翻倍 N耗时翻 4 倍Barnes-Hut 平缓得多。两条线在 N≈170 附近交叉左边朴素赢右边树赢。交叉点BH 耗时首次 ≤ 朴素落在N128 与 N192 之间约 170 粒子。也就是说绝大多数浏览器粒子 demo几十到一百多颗实际处在「朴素更快」的一侧。朴素法自身严格按 N² 增长8000 相对 125 耗时放大约 4350×与 64²≈4096 吻合而 Barnes-Hut 在 64000 时仍把每步压在 342ms——同量级下朴素法要近 10 秒。可复现命令仓库同目录_bench.js/_bench_small.js# Node 22 托管运行时复现上表 node _bench.js # 大 N 全量曲线含精度检查 node _bench_small.js # 小 N 交叉点细测图3把「树比朴素快几倍」画成曲线更直观。它在 170 粒子处穿过 y1 这条生死线此后一路向上到 8000 粒子已 9.6×外推 64000 粒子约 28.7×。为什么小 N 反而被反超被忽略的常数因子复盘的落脚点不在「谁赢」而在「赢在哪」。Barnes-Hut 的复杂度写成 O(n log n)但这是力计算的复杂度没算每帧重建四叉树的成本建树分配N 个质点约产生 1.3N 个内部节点对象每次都是一次堆分配质心归约每个节点要累加子节点质量与加权位置是另一遍遍历遍历下钻每个质点的受力要走一条从根到叶的路径包含栈操作与 θ 判断分支。这些开销与 N 近似成正比建树 O(n)、遍历 O(n log n)但系数不小。在小 N 时朴素法「N² 次力计算」本身才几千次浮点运算而建树那套固定流程已经吃掉更多时间——这就是为什么 N64 时树反而慢 1.75×。常数因子主导小 N渐进复杂度主导大 N两者各管一段没有谁「永远」占优。局限Barnes-Hut 不是免费午餐精度与边界别把「更快」理解成「无代价」。同一份基准里我顺手测了精度N2000、θ0.7 时Barnes-Hut 受力相对朴素法的RMS 相对误差仅 0.87%整体可信但最大相对误差达 116%——发生在极少数近距、深钻不到的质点上正是引力模拟里最该准的近距离交会。θ 越小误差越低、越慢θ 越大越快、误差越炸。这条曲线是你要自己调的旋钮不是默认值就万能。另外三个边界它不解决① 3D 要把四叉树换成八叉树常数因子更重② 它只加速「全对全」求和若你的力是短程的比如只和近邻作用空间哈希网格往往比树更直③ 它假设质点可聚合对非物理的、强各向的相互作用并不天然适用。本文只复盘了 2D 均匀分布的力计算耗时没碰积分器、没碰渲染结论的适用范围就到此为止。结论与下一步一个可复用的选型边界一句话方法论别因为「O(n log n)」就默认上树。先估你的粒子数——170 以下直接用朴素双重循环它更简单、零分配、在小 N 反而更快越过 170 再切 Barnes-Hut并显式调 θ 在你的精度预算内取最大。复杂度是路线图不是判决书掐表永远比背诵渐进符号可靠。开源地址矩阵门户GitHub - wangzifan396-wzf/WB: nano-tools: 1200 single-file, zero-dependency, local-first web utilities in one portal. Offline and private, nothing leaves your browser. Binary protocol parsers, crypto, dev, audio, visualization, productivity. · GitHub单文件工具聚合器GitHub - wangzifan396-wzf/nano-workbench: Single-file tabbed launcher for the nano-tools matrix - one tab, 382 curated tools (of 1228), instant switching. Zero-dep. Part of nano-tools. · GitHubGitHub 组织主页wangzifan396-wzf (WangZi) · GitHub