Ký hiệu lớn-o cho hàm `len()` trong Python là gì?

Question

thể trùng lặp:
Cost of len() function

Liệu len() lặp trên các đối tượng trong một danh sách và sau đó trở về đếm của họ? Do đó, hãy cho nó O (n).

Hoặc ....

Có một danh sách python giữ một số lượng của bất kỳ đối tượng được nối thêm vào nó và ra khỏi nó và sau đó chỉ cần quay trở lại này "đếm" khi len() được gọi là? Vì vậy, hãy cho nó O (1).

Answer 1

Danh sách Python biết chiều dài của nó; len mất O(1) time. Lists are actually arrays, không phải danh sách được liên kết như trong Lisp, trong đó length mất thời gian tuyến tính.

Answer 2

Đối với tất cả các đối tượng tích hợp xác định __len__(), nó sẽ là O (1). Nếu bạn thực hiện __len__() cho các đối tượng của riêng bạn, nó có thể là bất cứ điều gì.