O（N）速度和O（1）记忆的汉明数

O（N）速度和O（1）记忆的汉明数

这里首先要考虑的是直接切片枚举算法，例如，可以在此SO答案中]看到，枚举序列成员

(k,j,i)

的给定对数值（以 2 为 底
）附近的三元组，以便

target - delta < k*log2_5 + j*log2_3 + i < target +delta

在选择时逐步计算累积对数的

j

和

k

，使得

i

直接已知的。

因此，它是一个 N 2/3次_算法，一次生成 _N 2/3_宽的序列切片（

k*log2_5 + j*log2_3 +i

接近目标值，因此这些三元组构成填充有汉明序列三元组
1的四面体的外壳） ，表示每个产生的数字为 _O（1）

时间，从而在 O（N）的 摊销 时间和 O（N 2/3 ） 空间中产生 N个 序列成员。相对于基线Dijkstra的算法2而言
，这是没有任何改善的，它 具有相同的复杂度，甚至可以进行 非摊销
并具有更好的恒定因子。 __

为了使其具有 O（1） 空间，随着序列的进行，地壳宽度将需要变窄。但是，地壳越窄，枚举其三元组的机会就会越来越多- 这几乎就是您所要求的证明
。恒定的切片大小意味着对于整个 O（N 5/3 ） 摊销时间，使用 O（1） 空间算法，每个 O（1） 切片的 _O（N 2/3）_功。

---

这是该频谱上的两个端点：从 N 1次， _N 2/3_空间到 _N 0_空间， _N 5/3_时间摊销。

---

1这是Wikipedia的图像，具有对数垂直刻度：

从侧面看，这本质上是

(i,j,k)

在空间中拉伸的汉明序列四面体

(i*log2, j*log3,k*log5)

。如果是真正的3D图片，则图像有点歪斜。

编辑： 2似乎我忘记了必须对切片进行排序，因为它们是由 j，k 枚举无序生成的。这将 通过切片算法按顺序生成序列的 N 个数的最佳复杂性更改为
O（N 2/3 log N）_时间， _O（N 2/3）_空间，并使Dijkstra算法成为那里的赢家。但是，对于 _O（1） 切片，它不会更改
_O（N 5/3）_时间的上限。 __