algorithm - O(N) 速度和 O(1) 内存的汉明数

Question

免责声明:有很多关于它的问题，但我没有找到任何需要常量内存的问题。

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

是否有可能用 O(N) 时间和 O(1)(常数)内存生成第 N 个汉明数？在 generate 下，我指的是生成器，即你只能输出结果而不能读取之前生成的数字(在这种情况下内存将不是常量)。但是你可以保存一些常数。

我看到只有常量内存的最佳算法并不比 O(N log N) 好，例如，基于优先级队列。但是是否有数学证明不可能在 O(N) 时间内构造算法？

Answer 1

这里首先要考虑的是直接切片枚举算法，例如可以看到in this SO answer , 枚举三元组 (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 接近目标值，所以这些三元组形成了 tetrahedron 的外壳，填充了 Hamming sequence 三元组 ¹)，意思是 O (1) 每个生成数的时间，从而在 O(N) 摊销 时间和 O 中生成 N 个序列成员(N^2/3)-空间。这与基线 Dijkstra 算法 ² 没有任何改进，具有相同的复杂性，甚至非摊销和更好的常数因子。

为了使其成为 O(1) 空间，地壳宽度需要随着我们沿着序列前进而变窄。但是地壳越窄，在枚举它的三元组时就会出现越多的失误——这几乎就是你要求的证明。恒定切片大小意味着 O(N^2/3) 每个 O(1) 切片的工作，对于整体 O( N^5/3) 摊销时间，O(1) 空间算法。

这些是该频谱的两个端点:从 N¹ 时间开始，N^2/3-空间到 N⁰ 空间，N^5/3-时间，摊销。

---

¹ 这是 the image from Wikipedia ，具有对数垂直刻度:

这本质上是汉明序列三元组的四面体 (i,j,k)在空间中拉伸(stretch)为 (i*log2, j*log3, k*log5) ，从侧面看。图像有点歪，如果是真正的 3D 图片。

edit: ² 我好像忘记了切片必须排序，因为它们是由 j,k-枚举。这将通过切片算法按顺序生成序列的 N 数的最佳复杂度更改为 O(N^2/3 log N) 时间， O(N^2/3) 空间，并使 Dijkstra 算法在那里成为赢家。不过，对于 O(1) 个切片，它不会更改 O(N^5/3) 时间的上限。