企业官网建设流程全解析

你写了一个浏览器里的引力 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 粒子附近

我用种子化随机（mulberry32，seed=20260818）生成均匀分布的质点，固定软化 ε²=1、θ=0.7，在 Node 22 上对每个 N 跑 5 轮取中位数每步耗时（仅计时受力计算，含建树）。朴素法测到 8000，Barnes-Hut 测到 64000：

（带 * 为按 N² 外推，仅作量级参考，非实测点。）

图2：双对数坐标下，朴素法是一条斜率 2 的直线（每翻倍 N，耗时翻 4 倍）；Barnes-Hut 平缓得多。两条线在 N≈170 附近交叉：左边朴素赢，右边树赢。

交叉点（BH 耗时首次 ≤ 朴素）落在N=128 与 N=192 之间，约 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 粒子处穿过 y=1 这条生死线，此后一路向上，到 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² 次力计算」本身才几千次浮点运算，而建树那套固定流程已经吃掉更多时间——这就是为什么 N=64 时树反而慢 1.75×。常数因子主导小 N，渐进复杂度主导大 N，两者各管一段，没有谁「永远」占优。

局限：Barnes-Hut 不是免费午餐（精度与边界）

别把「更快」理解成「无代价」。同一份基准里我顺手测了精度：N=2000、θ=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. · GitHub
• GitHub 组织主页：wangzifan396-wzf (WangZi) · GitHub