O（N）速度和O（1）记忆的汉明数 [英] Hamming numbers for O(N) speed and O(1) memory

问题描述

免责声明：对此有很多疑问，但是我没有找到任何需要恒定内存的东西。

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory.

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

Hamming numbers is a numbers 2^i*3^j*5^k, where i, j, k are natural numbers.

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

Is there a possibility to generate Nth Hamming number with O(N) time and O(1) (constant) memory? Under generate I mean exactly the generator, i.e. you can only output the result and not read the previously generated numbers (in that case memory will be not constant). But you can save some constant number of them.

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

I see only best algorithm with constant memory is not better than O(N log N), for example, based on priority queue. But is there mathematical proof that it is impossible to construct an algorithm in O(N) time?

推荐答案

这里首先要考虑的问题是直接切片枚举算法，例如在此答案中，枚举序列成员给定对数值（ base 2 ）附近的三元组（k，j，i） 目标-增量< k * log2_5 + j * log2_3 + i< target + delta ，逐步计算累积对数，同时选择 j 和 k i 是直接已知的。

First thing to consider here is the direct slice enumeration algorithm which can be seen e.g. in this SO answer, enumerating the triples (k,j,i) in the vicinity of a given logarithm value (base 2) of a sequence member so that target - delta < k*log2_5 + j*log2_3 + i < target + delta, progressively calculating the cumulative logarithm while picking the j and k so that i is directly known.

因此它是 N ^2/3 时间算法一次生成 N ^2/3 宽的切片（使用 k * log2_5 + j * log2_3 + i 接近目标值，因此这些三元组构成了四面体填充为汉明序列三元组 ¹ ） ，表示每个产生的数字 O（1）时间，从而在 O（N） 摊销的中产生 N 个序列成员时间和 O（N ^2/3 ）-空间。相对于基线Dijkstra算法s ² ，具有相同的复杂度，甚至未摊销并且具有更好的恒定因子，也没有任何改善。

It is thus an N^2/3-time algo producing N^2/3-wide slices of the sequence at a time (with k*log2_5 + j*log2_3 + i close to the target value, so these triples form the crust of the tetrahedron filled with the Hamming sequence triples ¹), meaning O(1) time per produced number, thus producing N sequence members in O(N) amortized time and O(N^2/3)-space. That's no improvement over the baseline Dijkstra's algorithm ²  with the same complexities, even non-amortized and with better constant factors.

要使其为 O（1）空间，我们沿序列进行时，地壳宽度将需要缩小。但是，地壳越窄，枚举三元组的机会就越多-这几乎就是您所要求的证据。恒定的切片大小意味着对于 O（1）切片，每个 O（1）切片 O（N ^2/3 ） N ^5/3 ）摊销时间， O（1）空间算法。

To make it O(1)-space, the crust width will need to be narrowed as we progress along the sequence. But the narrower the crust, the more and more misses will there be when enumerating its triples -- and this is pretty much the proof you asked for. The constant slice size means O(N^2/3) work per the O(1) slice, for an overall O(N^5/3) amortized time, O(1) space algorithm.

这些是此频谱上的两个端点：从 N ¹ -time， N ^2/3 -空间到 N ⁰ 空间， N ^5/3 时间，摊销。

These are the two end points on this spectrum: from N¹-time, N^2/3-space to N⁰ space, N^5/3-time, amortized.

¹ 这是来自维基百科的图片，具有对数垂直刻度：

¹ Here's the image from Wikipedia, with logarithmic vertical scale:

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

This essentially is a tetrahedron of Hamming sequence triples (i,j,k) stretched in space as (i*log2, j*log3, k*log5), seen from the side. The image is a bit askew, if it's to be true 3D picture.

edit： ² 忘记了切片必须进行排序，因为它们是由 j，k 枚举无序生成的。这将通过切片算法依次产生序列 N 个数的最佳复杂度更改为 O（N ^2/3 log N）时间， O（N ^2/3 ）空间，并使Dijkstra的算法成为赢家。但是，对于 O（1）切片，它不会更改 O（N ^5/3 ）时间的上限。

edit: ² It seems I forgot that the slices have to be sorted, as they are produced out of order by the j,k-enumerations. This changes the best complexity for producing the sequence's N numbers in order via the slice algorithm to O(N^2/3 log N) time, O(N^2/3) space and makes Dijkstra's algorithm a winner there. It doesn't change the top bound of O(N^5/3) time though, for the O(1) slices.

这篇关于O（N）速度和O（1）记忆的汉明数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！