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在选择时逐步计算累积对数的jk,使得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)_时间的上限。 __

以上是 O(N)速度和O(1)记忆的汉明数 的全部内容, 来源链接: utcz.com/qa/415685.html

回到顶部