免责声明：有很多关于它的问题，但我没有找到任何需要恒定内存的问题。
汉明数是一个数字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(N 2/3 )空间中产生N个序列成员。 这与具有相同复杂性的基线 Dijkstra 算法 2相比没有任何改进，即使是非摊销且具有更好的常数因子。
为了使它成为O(1) -空间，随着我们沿着序列前进，地壳宽度需要变窄。但是地壳越窄，在列举它的三元组时，就会有越来越多的失误——这几乎就是你所要求的证明。恒定切片大小意味着O(N 2/3 )每个O(1)切片的工作量，对于整个O(N 5/3 ) 分摊时间，O(1)空间算法。
这些是该频谱上的两个端点：从N 1次，N 2/3次空间到N 0次，N 5/3次，摊销。
1这是来自 Wikipedia 的图片，具有对数垂直刻度：
从侧面看，这本质上是一个(i,j,k)在空间中拉伸的 Hamming 序列三元组的四面体。(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 )时间的上限。
