¿Cuál es la notación big-o para la función `len()` en Python?

Question

Duplicar posibles:
Cost of len() function

¿El len() iterar sobre los objetos en una lista y luego regresar a su recuento? Por lo tanto, dándole un O (n).

O ....

¿Tiene una lista de Python mantener un recuento de todos los objetos que se adjuntan a la misma y se retira de él y simplemente se devuelve este "recuento" cuando len() se llama? Así, dándole O (1).

Answer 1

Una lista de Python conoce su propia longitud; len toma O(1) time. Lists are actually arrays, listas no vinculadas como en Lisp, donde length toma tiempo lineal.

Answer 2

Para todos los objetos incorporados que definen __len__(), será O (1). Si implementa __len__() para sus propios objetos, podría ser cualquier cosa.