Tôi đã đăng chéo câu hỏi này trên trang web Redis và Pieter Noordhuis đã cung cấp câu trả lời ở đó, tôi sẽ đăng chéo ở đây:
Đúng rồi. Tập hợp được sắp xếp dựa vào RNG để xác định số cấp trên mỗi nút (đó là cấu trúc dữ liệu xác suất). Chèn / xóa một phần tử ở đầu danh sách bỏ qua có thể là O (1), trong khi hiệu suất trường hợp xấu nhất trên lý thuyết là O (N) (với mọi nút có cùng mức). Tuy nhiên, độ phức tạp theo thời gian phân bổ là O (log N) khi bạn tính đến sự phân bổ các cấp độ giữa các nút.
