这里首先要考虑的是直接切片枚举算法，例如，可以在此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）_时间的上限。 __
602392714
清零编程群
