Numeri di Hamming per la velocità O (N) e memoria O (1)

Question

Disclaimer: ci sono molte domande a riguardo, ma non ne ho trovate nessuna con il requisito di memoria costante.

I numeri di Hamming sono numeri 2^i*3^j*5^k, dove i, j, k sono numeri naturali.

Esiste la possibilità di generare il numero Nth Hamming con il tempo O (N) e la memoria O (1) (costante)? Sotto generate intendo esattamente il generatore, cioè si può solo emettere il risultato e non leggere i numeri precedentemente generati (in tal caso la memoria non sarà costante). Ma puoi salvare un numero costante di loro.

Vedo che solo l'algoritmo migliore con memoria costante non è migliore di O (N log N), ad esempio, in base alla coda di priorità. Ma c'è una prova matematica che è impossibile costruire un algoritmo in tempo O (N)?

Answer 1

Prima cosa da considerare qui è l'algoritmo di enumerazione della porzione diretta che può essere visto ad es. in this SO answer, enumerare le triple (k,j,i) nelle vicinanze di un dato valore logaritmo (base 2) di un membro di sequenza in modo che target - delta < k*log2_5 + j*log2_3 + i < target + delta, calcolando progressivamente il logaritmo cumulativo mentre raccogliendo il j e k modo che i è direttamente conosciuto.

È quindi un N ^2/3 -time algo produrre N ^2/3 fette -wide della sequenza alla volta (con k*log2_5 + j*log2_3 + i vicino al valore di riferimento, così questi triple formano la crosta del tetrahedron riempito con i Hamming sequence triple  ), cioè O (1) volta al numero prodotta, producendo così membri N sequenza in O (N)amor tempo e O (N ^2/3) -space. Questo non è un miglioramento rispetto all'algoritmo di Dijkstra di base     con le stesse complessità, anche non ammortizzato e con fattori costanti migliori.

Per rendere O (1) -space, la larghezza della crosta dovrà essere ridotta man mano che avanza lungo la sequenza. Ma più stretta è la crosta, più errori ci saranno quando enumereremo i suoi tripli - e questa è praticamente la prova che hai richiesto per. La dimensione fetta costante significa O (N ^2/3) lavoro per la O (1) slice, per complessivi O (N ^5/3) tempo ammortizzato, O (1) algoritmo spaziale.

Questi sono i due punti di estremità di questo spettro: da N -time, N ^2/3 -space a N spazio, N ^5/3 -time, ammortizzato.

---

Ecco the image from Wikipedia, con scala logaritmica verticale:

Questo è essenzialmente un tetraedro di sequenza Hamming triplica (i,j,k) allungata nello spazio come (i*log2, j*log3, k*log5), visto dal lato. L'immagine è un po 'storta, se deve essere vera immagine 3D.

edit: Sembra ho dimenticato che le fette devono essere ordinati, come sono prodotte fuori dell'ordine da parte del j, k -enumerations. Questo cambia il miglior complessità per la produzione di N numeri della sequenza in ordine tramite l'algoritmo fetta di O (N ^2/3 log N) tempo, O (N ^2/3) spazio e rende Dijkstra di algoritmo un vincitore lì. Non modifica il limite superiore di O (N ^5/3) tempo, per le fette O (1).