Числа Хэмминга для скорости O(N) и памяти O(1)

Отказ от ответственности: вопросов по этому поводу много, но я не нашел ни одного с требованием постоянной памяти.

Числа Хэмминга — это числа 2^i*3^j*5^k, где i, j, k — натуральные числа.

Есть ли возможность сгенерировать N-е число Хэмминга с O (N) временем и O (1) (постоянной) памятью? Под генерацией я подразумеваю именно генератор, т.е. можно только выводить результат, а не читать ранее сгенерированные числа (в этом случае память будет непостоянной). Но можно сохранить какое-то постоянное их количество.

Я вижу только лучший алгоритм с постоянной памятью не лучше, чем O(N log N), например, на основе приоритетной очереди. Но есть ли математическое доказательство невозможности построить алгоритм за время O(N)?


algorithm time-complexity big-o space-complexity hamming-numbers
person vladon    schedule 12.05.2016    source источник
comment
stackoverflow.com/q/12480291/77567   -  person rob mayoff    schedule 13.05.2016
comment
Это интересный вопрос, но, возможно, вам повезет больше, если вы получите ответ на cs.stackexhange.com, поскольку, вероятно, это невозможно, и вам нужны доказательства.   -  person Paul Hankin    schedule 13.05.2016
comment
какой алгоритм памяти O (1) O (N log N) вы упомянули? упоминаемый вами PQ занимает ~ N ^ (2/3) места. и, кстати, правильный стандартный алгоритм (из-за Дейкстры) - время O (N). даже алгоритм перепроизводства, на который вы, вероятно, ссылаетесь, может быть O (N) при использовании правильно производительного PQ с O (1) poop и O (1) вставкой.   -  person Will Ness    schedule 20.05.2016
comment
@robmayoff это тоже не память O (1) из-за циклов обратной связи в каждом узле. (и h/2 по-прежнему ~N^(2/3), как и h/5.)   -  person Will Ness    schedule 20.05.2016

Ответы (1)


arrow_upward
5
arrow_downward

Первое, что нужно рассмотреть, это алгоритм прямого перечисления срезов, который можно увидеть, например. в этом ответе SO, перечисление троек (k,j,i) вблизи заданного значения логарифма (по основанию 2) члена последовательности, так что target - delta < k*log2_5 + j*log2_3 + i < target + delta, постепенное вычисление кумулятивного логарифма при выборе j и k так, чтобы i было непосредственно известный.

Таким образом, это N2/3алгоритм, создающий N2/3срезы последовательности шириной за раз (при этом k*log2_5 + j*log2_3 + i близко к целевому значению, поэтому эти тройки образуют кору тетраэдра заполнены тройками последовательности Хэмминга 1), что означает O(1) раз на произведенное число, таким образом создавая N членов последовательности за O(N) амортизированное время и O(N2/3)-пробел. Это ничем не лучше базового алгоритма Дейкстры 2  с той же сложностью, даже без амортизации и с лучшими постоянными факторами.

Чтобы сделать его O(1)-пространством, ширину коры нужно будет сужать по мере продвижения по последовательности. Но чем уже кора, тем больше и больше промахов будет при перечислении ее троек -- и это практически то доказательство, о котором вы просили. Постоянный размер среза означает, что O(N2/3) работает на каждый срез O(1) при общем O( N5/3) амортизированное время, O(1) пространственный алгоритм.

Это две конечные точки на этом спектре: от N1-время, N2/3-пространство до N0 пробела, N5/3-раза, амортизировано.

1 Вот изображение из Википедии, с логарифмическим вертикальным масштабом:

введите здесь описание изображения

По сути, это тетраэдр троек последовательности Хэмминга (i,j,k), вытянутый в пространстве как (i*log2, j*log3, k*log5), если смотреть сбоку. Изображение немного кривое, если говорить о реальном 3D изображении.

edit: 2 Кажется, я забыл, что срезы должны быть отсортированы, так как они создаются не по порядку с помощью j,k-перечисления . Это изменяет лучшую сложность для создания N номеров последовательности в порядке с помощью алгоритма среза на O(N2/3 log N) времени, O(N2/3) и делает алгоритм Дейкстры победителем. Тем не менее, это не изменяет верхнюю границу времени O(N5/3) для срезов O(1).

person Will Ness    schedule 20.05.2016