Tôi gặp một câu hỏi khi tôi giải quyết this LeetCode problem. Mặc dù giải pháp của tôi đã được hệ thống chấp nhận, tôi vẫn không có ý tưởng nào sau khi tìm kiếm trực tuyến cho câu hỏi sau: What is the time complexity of dict.keys() operation? Nó có trả về một cái nhìn của các phím hoặc danh sách thực (các cửa hàng trong bộ nhớ) của các khóa không?Độ phức tạp của dict.keys trong Python là bao nhiêu?
Trong Python 2, đó là O (n) và nó tạo danh sách mới. Trong Python 3, nó là O (1), nhưng nó không trả về một danh sách. Để vẽ một phần tử ngẫu nhiên từ số keys của dict, bạn cần phải chuyển đổi nó thành một danh sách.
Có vẻ như bạn có thể đang sử dụng random.choice(d.keys()) cho phần 3 của vấn đề đó. Nếu vậy, đó là O (n), và bạn đã nhận nó sai. Bạn cần triển khai bảng băm của riêng mình hoặc duy trì một danh sách các phần tử riêng biệt mà không phải hy sinh các trường hợp chèn và xóa O (1) trung bình.
Tôi đã sử dụng 'return self.elements.keys() [randint (0, len (self.elements) - 1)]' và nó đã được chấp nhận ('self.elements là một đối tượng dict'). – Jason
@ Jason: Vâng, đó không phải là O (1). – user2357112
Như bạn đã nói "Trong Python 3, nó là O (1)". Nếu 'self.elements.keys()' là 'O (1)', thì toàn bộ biểu thức sẽ chạy trong 'O (1) '. Nếu tôi phạm sai lầm, hãy sửa tôi :) – Jason
Độ phức tạp của nó là '0 (1)' trong Python 3.x. Trong Python 2.x, nó trả về một danh sách để populating nó hoặc thực hiện một số tra cứu trên nó có '0 (n)'. – ozgur
Bạn đang hỏi về Python2 hay Python3? –
@ ozgur - Đúng, nhưng 'cho _ trong {} .keys(): pass' là' O (n) 'trong cả hai phiên bản. –