Số Hamming cho tốc độ O (N) và O (1)

Question

Tuyên bố từ chối: có nhiều câu hỏi về nó, nhưng tôi không tìm thấy bất kỳ yêu cầu nào về bộ nhớ không đổi.

Số Hamming là một số 2^i*3^j*5^k, trong đó i, j, k là số tự nhiên.

Có khả năng tạo số Nth Hamming với O (N) và O (1) (hằng số) bộ nhớ không? Theo tạo ra tôi có nghĩa là chính xác máy phát điện, tức là bạn chỉ có thể xuất kết quả và không đọc các số đã tạo trước đó (trong bộ nhớ trường hợp đó sẽ không phải là hằng số). Nhưng bạn có thể tiết kiệm một số số liên tục của chúng.

Tôi chỉ thấy thuật toán tốt nhất với bộ nhớ liên tục không tốt hơn O (N log N), ví dụ, dựa trên hàng đợi ưu tiên. Nhưng có bằng chứng toán học nào không thể xây dựng một thuật toán trong thời gian O (N)?

Answer 1

Điều đầu tiên cần xem xét ở đây là thuật toán liệt kê slice trực tiếp có thể xem được, ví dụ: in this SO answer, liệt kê bộ ba (k,j,i) trong vùng lân cận của một giá trị logarit nhất định (cơ sở 2) của một thành viên chuỗi để target - delta < k*log2_5 + j*log2_3 + i < target + delta, dần dần tính logarit tích lũy khi chọn j và k để i được trực tiếp biết.

Như vậy một N ^2/3 -time algo sản xuất N ^2/3 lát -wide của chuỗi tại một thời điểm (với k*log2_5 + j*log2_3 + i gần với giá trị mục tiêu, do đó, những hình gấp ba lớp vỏ của tetrahedron tràn đầy Hamming sequence gấp ba  ), có nghĩa O (1) thời gian cho mỗi số sản xuất, do đó sản xuất thành viên N chuỗi trong O (N)amor tized thời gian và O (N ^2/3) -space. Đó không phải là cải tiến so với thuật toán cơ bản của Dijkstra     với cùng độ phức tạp, thậm chí không phân bổ và có các yếu tố không đổi tốt hơn.

Để làm cho nó O (1) -space, chiều rộng lớp vỏ sẽ cần phải được thu hẹp khi chúng tôi tiến hành dọc theo trình tự. Nhưng lớp vỏ càng hẹp, càng có nhiều lần nhớ sẽ xuất hiện khi liệt kê bộ ba của nó - và đây là bằng chứng bạn yêu cầu cho. Kích thước miếng liên tục có nghĩa O (N ^2/3) việc theo O (1) lát, cho một tổng thể O (N ^5/3) thời gian khấu hao, O (1) thuật toán không gian.

Đây là hai điểm cuối trên quang phổ này: từ N -time, N ^2/3 -space để N không gian, N ^5/3 -time, được phân bổ.

---

Dưới đây là the image from Wikipedia, với quy mô dọc logarit:

Đây thực chất là một tứ diện của chuỗi Hamming TripleS (i,j,k) kéo dài trong không gian như (i*log2, j*log3, k*log5), nhìn từ phía bên. Hình ảnh hơi bị xiên, nếu đó là hình ảnh 3D thực sự.

chỉnh sửa: Có vẻ như tôi đã quên rằng lát phải được sắp xếp, vì chúng được sản xuất ra khỏi trật tự bởi j, k -enumerations. Điều này thay đổi mức độ phức tạp tốt nhất cho sản xuất N số của dãy theo thứ tự thông qua các thuật toán lát để O (N ^2/3 log N) thời gian, O (N ^2/3) không gian và làm cho Dijkstra thuật toán một người chiến thắng ở đó. Nó không thay đổi giới hạn trên cùng của O (N ^5/3) mặc dù, đối với các lát cắt O (1).