Độ phức tạp của các hoạt động bộ python?

Question

Độ phức tạp về thời gian của mỗi hoạt động thiết lập của python trong ký hiệu Big O là gì?

Tôi đang sử dụng số set type của Python cho một thao tác trên một số lượng lớn các mục. Tôi muốn biết hiệu suất của từng hoạt động sẽ bị ảnh hưởng như thế nào bởi kích thước của bộ này. Ví dụ, add, và thử nghiệm cho thành viên:

myset = set() 
myset.add('foo') 
'foo' in myset 

Googling xung quanh đã không bật lên bất kỳ tài nguyên, nhưng có vẻ như hợp lý rằng sự phức tạp thời gian để thực hiện bộ Python có thể đã được xem xét cẩn thận.

Nếu nó tồn tại, một liên kết đến một cái gì đó như this sẽ là tuyệt vời. Nếu không có thứ gì như thế này, thì có lẽ chúng ta có thể giải quyết nó?

Dấu phụ để tìm độ phức tạp thời gian của tất cả đặt hoạt động.

Answer 1

Hoạt động in phải độc lập với kích thước của vùng chứa, ví dụ: O (1) - được cung cấp hàm băm tối ưu. Điều này phải là gần như đúng đối với chuỗi Python. Chuỗi băm luôn luôn là quan trọng, Python phải thông minh ở đó và do đó bạn có thể mong đợi các kết quả gần như tối ưu.

Answer 2

Theo Python wiki: Time complexity, đặt được triển khai dưới dạng hash table. Vì vậy, bạn có thể mong muốn tra cứu/chèn/xóa trong số O (1) trung bình. Trừ khi hệ số tải của bảng băm của bạn quá cao, thì bạn phải đối mặt với va chạm và O (n).

P.S. vì một lý do nào đó họ yêu cầu O (n) cho hoạt động xóa trông giống như một kiểu nhập nhầm.

P.P.S. Điều này đúng với CPython, pypy là different story.