Qual è la notazione big-o per la funzione `len()` in Python?

Question

Eventuali duplicati:
Cost of len() function

Does len() iterate nel corso degli oggetti in una lista e poi tornare il loro numero? Così dandogli un O (n).

O ....

Fa un elenco di pitone tenere un conteggio di tutti gli oggetti che vengono aggiunti ad esso e rimossi da esso e poi semplicemente restituire questo "conteggio" quando len() si chiama? Così dandogli O (1).

Answer 1

Una lista Python conosce la propria lunghezza; len prende O(1) time. Lists are actually arrays, non elenchi collegati come in Lisp, dove length richiede tempo lineare.

Answer 2

Per tutti gli oggetti incorporati che definiscono __len__(), sarà O (1). Se si implementa __len__() per i propri oggetti, potrebbe essere qualsiasi cosa.