O(N)速度和O(1)存储器的汉明数

Question

免责声明:关于它有很多问题,但我没有找到任何需要恒定记忆的问题.

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

是否有可能在O(N)时间和O(1)(常数)存储器中产生第N个汉明数？在生成下我的意思是完全生成器,即你只能输出结果而不读取先前生成的数字(在这种情况下,内存将不是常量).但是你可以保存一些常数.

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

Answer 1

这里首先要考虑的是直接切片枚举算法，例如在这个 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接近目标值，因此这些三元组形成了填充有汉明序列三元组 ¹的四面体的外壳） ，意味着每个产生的数字O(1)时间，从而在O(N)分摊时间和O(N ^2/3 ) -空间中产生N 个序列成员。这  与具有相同复杂度的基线 Dijkstra 算法²相比没有任何改进 ，即使是非摊销且具有更好的常数因子。

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

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

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

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

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