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

免责声明：关于它有很多问题，但是我没有发现任何需要持续存储的问题。

汉明数是一个数字2^i*3^j*5^k，其中i，j，k是自然数。

是否有可能用O（N）时间和O（1）（恒定）内存生成第N个汉明数？在“生成”下，我指的是生成器，即您只能输出结果而不能读取先前生成的数字（在这种情况下，内存将不是恒定的）。但是您可以保存一些恒定数量的它们。

我看到，例如，基于优先级队列，仅具有恒定内存的最佳算法并不比O（N log N）好。但是，是否有数学证据证明不可能在O（N）时间内构造算法？

这里首先要考虑的是直接切片枚举算法，例如，可以在此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（N2/3）空间中产生 N个序列成员。相对于基线Dijkstra的算法2而言

，这是没有任何改善的，它具有相同的复杂度，甚至可以进行 非摊销

并具有更好的恒定因子。 _

为了使其具有 O（1） 空间，随着序列的进行，地壳宽度将需要变窄。但是，地壳越窄，枚举其三元组的机会就会越来越多- 这几乎就是您所要求的证明

。恒定的切片大小意味着对于整个 O（N5/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）_时间的上限。 __