算法复杂度与性能_800万像素的处理开销

这一篇算三笔账：算法要跑多少遍、每个像素要占多少内存、浏览器真正把时间花在哪里，顺带说明 800 万像素上限是怎么来的。

时间复杂度：曲线生成一遍，像素搬运一遍

结论先给：本站的置换算法是严格的线性复杂度 O(N)，其中 N = W × H 是像素总数。整条链路只有两遍，第一遍沿广义吉尔伯特曲线（Gilbert curve，希尔伯特曲线的矩形推广）走遍每个格子，得到曲线序 order；第二遍按 order 把每个像素搬到新位置。

两遍都是单层循环，循环次数正比于 N，中间没有嵌套的扫描，也没有逐对比较。耗时与图片内容无关：纯色图和满屏噪点的图，像素数量一样，搬运次数就一样，不会因为画面复杂而变慢。

写成公式就是 out[order[(i + k) mod N]] = in[order[i]]，解混淆把等号两端对调。每个像素只被读一次、写一次，没有重复访问。置换流程与伪代码那一篇给出了可以照着实现的版本。

空间账：每个像素要留 12 字节

内存比时间更容易成为瓶颈，所以这笔账要算细。曲线序用 Uint32Array 保存，存的是线性下标 y * width + x，每个下标 4 字节，共 4N 字节。输入像素缓冲 4N 字节（每个像素的 RGBA 四个通道各 1 字节），输出像素缓冲同样是 4N 字节。

三份加起来：4N + 4N + 4N = 12N 字节。按 1 MB = 1 048 576 字节换算，200 万像素与 800 万像素两档分别是：

200 万像素：12 × 2 000 000 = 24 000 000 字节；24 000 000 ÷ 1 048 576 ≈ 22.89 MB。
800 万像素：12 × 8 000 000 = 96 000 000 字节；96 000 000 ÷ 1 048 576 ≈ 91.55 MB。

同样这两个数，如果按 1 MB = 1 000 000 字节算，得到的是 24 MB 和 96 MB。常见说法里的「200 万像素约 24 MB 临时内存」用的就是这个口径，两者只是换算标准不同，不是估算有出入。

注意 12N 之外还有画布本身。浏览器为画布分配的内存、编码阶段产生的中间副本都不在这笔账里，所以实际占用通常高于 12N 这个下限。

要点速记

时间：曲线生成一遍加像素搬运一遍，都是 O(N)，与画面内容无关。
空间：曲线序 4N 加上输入输出各 4N，合计 12N 字节。
瓶颈：置换循环是纯内存操作，画布读取与 JPEG 编码更贵。
上限：800 万像素、单边 4000 像素，超限先等比缩放，从此不再无损。

不同分辨率的内存对照表

把常见尺寸代进 12N，上限为什么定在 800 万像素就一目了然了。下表一律按 1 MB = 1 048 576 字节换算，曲线序为 4N，像素缓冲是输入与输出两份共 8N。

常见分辨率下的临时内存占用（不含画布本身）
分辨率	像素数 N	曲线序 4N	像素缓冲 8N	合计 12N
640 × 480	307 200	1 228 800 B ≈ 1.17 MB	2 457 600 B ≈ 2.34 MB	3 686 400 B ≈ 3.52 MB
1280 × 720	921 600	3 686 400 B ≈ 3.52 MB	7 372 800 B ≈ 7.03 MB	11 059 200 B ≈ 10.55 MB
1920 × 1080	2 073 600	8 294 400 B ≈ 7.91 MB	16 588 800 B ≈ 15.82 MB	24 883 200 B ≈ 23.73 MB
2048 × 1536	3 145 728	12 582 912 B = 12.00 MB	25 165 824 B = 24.00 MB	37 748 736 B = 36.00 MB
4000 × 3000	12 000 000	48 000 000 B ≈ 45.78 MB	96 000 000 B ≈ 91.55 MB	144 000 000 B ≈ 137.33 MB

最后一行是越界的例子：4000 × 3000 有 1200 万像素，超过 800 万的上限，实际处理前会先被缩小，这一行只是用来说明不设上限要付出什么代价。作为参照，1920 × 1080 的位移量 k 是 1 281 555，2048 × 1536 的 k 是 1 944 167，两者都来自同一个由 N 决定的算式。

曲线生成：递归深度只有 O(log) 级

曲线生成用的是分治递归，看上去比置换循环复杂，但它不是性能瓶颈。原因在分割方式：每一步都把当前矩形的两条边向量各取一半，也就是 ax2 = floor(ax / 2)、bx2 = floor(bx / 2)，每次递归都让边长减半。

边长减半意味着递归层数只跟边长的二进制位数有关。4000 像素宽的图，大约 12 层就落到 w === 1 或 h === 1 的平凡填充分支，整体深度是 O(log max(W, H)) 级别，而不是 O(W × H)。

再看访问总次数：每个格子只在最底层的平凡分支里被记录一次，所以生成过程本身也是 O(N)，只是常数比置换循环略大。想直观看到每一层怎么切分，可以打开吉尔伯特曲线可视化，输入任意宽高观察路径。

还要区分两件事：递归深度小，不等于曲线简单。同一条曲线恰好走遍每个格子一次，不交叉也不遗漏，这个双射性质才是算法可逆的基础。

真正的大头在画布与编码

置换循环只做内存读写，而它的前后两步都要碰画布与编码器：getImageData 把画布内容读回 CPU 侧缓冲，toBlob 把结果重新编码成 JPEG，中间还夹着色彩空间转换与通道排列。从结构上看，这两步的开销普遍高于那两遍线性置换。

这里给的是量级判断，不是实测数值。不同设备、不同浏览器、不同图片尺寸下的绝对耗时差异很大，写死一个毫秒数没有参考价值。能确定的方向是：图片边长减半，置换部分的计算量降到四分之一；编码部分的收益通常没这么快，因为它还受压缩率影响。

还有一个反直觉的现象值得知道：混淆后的 JPEG 往往比原图更大。像素被打乱后空间相关性被破坏，JPEG 的预测与熵编码效率下降，编码器反而要做更多工作。这不是 bug，是置乱的必然结果，输出格式与画质那一篇有更细的对照。

处理上限：800 万像素与单边 4000 像素

两个上限同时生效：单张图片像素数不超过 8 000 000，单边长度不超过 4000 像素。前者对应 12N ≈ 92 MB 的临时内存量级，后者是为了避免出现一条极长的边，让画布尺寸在某些浏览器上直接被拒绝。

超限图片不会报错了事，而是先等比缩小再处理。缩放系数取三个约束里最小的那个：像素数约束 sqrt(8 000 000 / N)、宽度约束 4000 / W、高度约束 4000 / H，再用它乘原宽高并四舍五入。以 4000 × 3000 为例，像素约束算出系数约 0.8165，目标尺寸约 3266 × 2449，落回 800 万以内。

缩放要重绘画布并重新编码，像素值已经改变，因此这条链路不再是无损的。原图进去、缩放结果出来，再解混淆也回不到原始像素，原因可以对照可逆性与误差分析。

如果对无损有硬要求，正确做法是自己在本地先把图裁到上限以内，并在导出时选择 PNG，保证全程不触发缩放。

移动端的现实约束

手机浏览器的可用内存比桌面少，而且标签页被系统回收时页面会整体重载，正在跑的图直接丢失。大图在移动端最大的风险不是慢，而是中途页面刷掉、结果拿不到。

三条能立刻用上的建议：

先在相册里把图裁小或降低一档分辨率，再交给工具处理，尽量不触发自动缩放。
一次只处理一张，处理期间不要切走标签页、不要锁屏，也不要让其他占内存的应用留在后台。
需要多轮处理时，直接保留 PNG 中间文件，避免 JPEG 反复转存把误差叠上去。

如果出现点了按钮没反应、页面白屏或结果异常，先按故障排查手册里的现象对号入座，多数情况是尺寸或格式问题，而不是算法本身出错。

为什么用 Uint32Array 与逐字节拷贝

原始实现把曲线序存成 [x, y] 坐标数组，再用 Array.prototype.slice 逐像素取出一段再写入。改成整型下标数组加逐字节直写之后，结果逐字节一致，但内存与耗时都降了下来。

两处改动的收益来源不同。曲线序从「每格一个二元数组」变成「每格一个 32 位整数」，省掉的是数组对象与坐标元数据；逐字节直写省掉的是每次拷贝都新建一个临时数组。两处都没动算法本身：曲线还是那条曲线，位移量还是 k = round((√5 − 1) / 2 × W × H)。

这类优化的意义在于把预算还给真正昂贵的部分。当单个像素的成本被压到几次内存访问，800 万像素的置换循环就不会成为用户等待的理由，值得继续打磨的是画布与编码。

这些数字的边界

以上全部是结构与量级分析：复杂度、字节数、递归层数都由公式推出，可以逐项复核；而「哪一步更慢」「手机上会不会崩」只给出方向性判断。实际耗时随设备、浏览器、图片内容与当时的内存压力变化很大，本文的数字不是性能承诺。

还有两点容易忽略。同一组数字下，1920 × 1080 与 1080 × 1920 的 N 相同、k 也相同，但曲线形状不同，混淆结果完全不同，所以横竖不是简单的旋转关系。另外，性能优化不会改变安全边界：算法公开、无密钥、可逆，任何人都能解混淆，它适合用来提高直接复用的成本，不适合保护真正敏感的内容。