Trang này ghi lại độ phức tạp về thời gian [còn gọi là "Big O" hoặc "Big Oh"] của các hoạt động khác nhau trong CPython hiện tại. Các triển khai Python khác [hoặc các phiên bản CPython cũ hơn hoặc vẫn đang được phát triển] có thể có các đặc điểm hiệu suất hơi khác một chút. Tuy nhiên, nhìn chung có thể an toàn khi cho rằng chúng không chậm hơn hệ số O[log n]
Nói chung, 'n' là số phần tử hiện có trong vùng chứa. 'k' là giá trị của tham số hoặc số phần tử trong tham số
Trường hợp trung bình giả định các tham số được tạo đồng đều một cách ngẫu nhiên
Bên trong, một danh sách được biểu diễn dưới dạng một mảng; . Nếu bạn cần thêm/xóa ở cả hai đầu, hãy cân nhắc sử dụng bộ sưu tập. deque thay vì
Hoạt động
trường hợp trung bình
Trường hợp xấu nhất được khấu hao
Sao chép
Trên]
Trên]
Nối[1]
Ô[1]
Ô[1]
Pop cuối cùng
Ô[1]
Ô[1]
Pop trung gian[2]
Trên]
Trên]
Chèn
Trên]
Trên]
Nhận vật phẩm
Ô[1]
Ô[1]
Thiết lập các mục
Ô[1]
Ô[1]
Xóa mục
Trên]
Trên]
lặp lại
Trên]
Trên]
Nhận lát
Được]
Được]
Del Slice
Trên]
Trên]
Đặt lát cắt
O[k+n]
O[k+n]
Gia hạn[1]
Được]
Được]
Loại
O[n log n]
O[n log n]
nhân
O[n]
O[n]
x tính bằng giây
Trên]
tối thiểu [s], tối đa [s]
Trên]
Nhận chiều dài
Ô[1]
Ô[1]
Một deque [hàng đợi hai đầu] được biểu diễn bên trong dưới dạng danh sách liên kết kép. [Chà, một danh sách các mảng chứ không phải các đối tượng, để đạt hiệu quả cao hơn. ] Cả hai đầu đều vào được, nhưng nhìn vào giữa còn chậm, thêm bớt vào giữa còn chậm hơn
Hoạt động
trường hợp trung bình
Trường hợp xấu nhất được khấu hao
Sao chép
Trên]
Trên]
nối thêm
Ô[1]
Ô[1]
appendleft
Ô[1]
Ô[1]
nhạc pop
Ô[1]
Ô[1]
popleft
Ô[1]
Ô[1]
gia hạn
Được]
Được]
mở rộng trái
Được]
Được]
quay
Được]
Được]
gỡ bỏ
Trên]
Trên]
Xem dict - việc triển khai có chủ ý rất giống nhau
Hoạt động
trường hợp trung bình
Trường hợp xấu nhất
ghi chú
x tính bằng giây
Ô[1]
Trên]
công đoàn. t
O[len[s]+len[t]]
ngã tư
O[min[len[s], len[t]]]
O[len[s] * len[t]]
thay thế "min" bằng "max" nếu t không phải là một bộ
Nhiều giao lộ s1&s2&. &sn
[n-1]*O[l] trong đó l là max[len[s1],. ,len[sn]]
sự khác biệt s-t
O[len[s]]
s. Difference_update[t]
O[len[t]]
Sự khác biệt đối xứng s^t
O[len[s]]
O[len[s] * len[t]]
s. symmetric_difference_update[t]
O[len[t]]
O[len[t] * len[s]]
Như đã thấy trong mã nguồn, độ phức tạp của chênh lệch cài đặt s-t hoặc s. sự khác biệt [t] [set_difference[]] và sự khác biệt được đặt tại chỗ s. khác biệt_update[t] [set_difference_update_internal[]] khác nhau. Cái đầu tiên là O[len[s]] [đối với mọi phần tử trong s, hãy thêm nó vào tập hợp mới, nếu không có trong t]. Cái thứ hai là O[len[t]] [đối với mọi phần tử trong t hãy xóa nó khỏi s]. Vì vậy, phải cẩn thận xem cái nào được ưu tiên hơn, tùy thuộc vào bộ nào dài nhất và liệu có cần một bộ mới hay không
- Để thực hiện các hoạt động thiết lập như s-t, cả s và t cần phải được thiết lập. Tuy nhiên, bạn có thể thực hiện phương thức tương đương ngay cả khi t là bất kỳ lần lặp nào, ví dụ: s. sự khác biệt [l], trong đó l là một danh sách
Thời gian trường hợp trung bình được liệt kê cho các đối tượng dict giả định rằng hàm băm cho các đối tượng đủ mạnh để không xảy ra va chạm. Trường hợp trung bình giả định rằng các khóa được sử dụng trong tham số được chọn ngẫu nhiên thống nhất từ tập hợp tất cả các khóa
Lưu ý rằng có một đường dẫn nhanh cho các ký tự [trong thực tế] chỉ xử lý các phím str; . một chương trình điển hình kết thúc nhanh như thế nào
Hoạt động
trường hợp trung bình
Trường hợp xấu nhất được khấu hao
tốt bụng
Ô[1]
Trên]
Sao chép[3]
Trên]
Trên]
Nhận vật phẩm
Ô[1]
Trên]
Đặt Mục[1]
Ô[1]
Trên]
Xóa mục
Ô[1]
Trên]
Lặp lại[3]
Trên]
Trên]
[1] = Các hoạt động này dựa trên phần "Được khấu hao" của "Trường hợp xấu nhất được khấu hao". Các hành động riêng lẻ có thể mất nhiều thời gian đáng ngạc nhiên, tùy thuộc vào lịch sử của vùng chứa
[2] = Lấy phần tử trung gian tại chỉ mục k từ danh sách kích thước n sẽ dịch chuyển tất cả các phần tử sau k sang trái một vị trí bằng cách sử dụng memmove. n - k phần tử phải được di chuyển, vì vậy phép toán là O[n - k]. Trường hợp tốt nhất là bật phần tử thứ hai đến phần tử cuối cùng, cần một lần di chuyển, trường hợp xấu nhất là bật phần tử đầu tiên, bao gồm n - 1 lần di chuyển. Trường hợp trung bình cho giá trị trung bình của k là bật phần tử ở giữa danh sách, thực hiện các phép toán O[n/2] = O[n]
[3] = Đối với các hoạt động này, trường hợp xấu nhất n là kích thước tối đa mà vùng chứa từng đạt được, thay vì chỉ kích thước hiện tại. Ví dụ: nếu N đối tượng được thêm vào từ điển, sau đó N-1 bị xóa, từ điển sẽ vẫn có kích thước cho N đối tượng [ít nhất] cho đến khi một lần chèn khác được thực hiện