Complejidad de list.index (x) en Python

Me refiero a esto: http://docs.python.org/tutorial/datastructures.html

¿Cuál sería el tiempo de list.index(x) de la función list.index(x) en términos de notación O grande?

Es O (n), también echa un vistazo a: http://wiki.python.org/moin/TimeComplexity

Esta página documenta la complejidad del tiempo (también conocida como “Big O” o “Big Oh”) de varias operaciones en el CPython actual. Otras implementaciones de Python (o versiones de CPython más antiguas o aún en desarrollo) pueden tener características de rendimiento ligeramente diferentes. Sin embargo, generalmente es seguro asumir que no son más lentos en más de un factor de O (registro n) …

Según dicha documentación:

 list.index(x) 

Devuelve el índice en la lista del primer elemento cuyo valor es x. Es un error si no hay tal artículo.

Lo que implica buscar. Efectivamente estás haciendo x in s pero en lugar de devolver True o False , estás devolviendo el índice de x . Como tal, me gustaría ir con la complejidad de tiempo enumerada de O (n).

Cualquier implementación de lista tendrá una complejidad O (n) para una búsqueda lineal (por ejemplo, list.index). Aunque tal vez haya algunas implementaciones extravagantes que empeoren …

Puede mejorar la complejidad de la búsqueda utilizando diferentes estructuras de datos, como listas ordenadas o conjuntos. Estos se suelen implementar con árboles binarios. Sin embargo, estas estructuras de datos ponen restricciones en los elementos que contienen. En el caso de un árbol binario, los elementos deben ser ordenados, pero el costo de búsqueda baja a O (log n).

Como se mencionó anteriormente, busque aquí los costos de tiempo de ejecución de las estructuras de datos estándar de Python: http://wiki.python.org/moin/TimeComplexity

La documentación proporcionada anteriormente no cubre list.index ()

a mi entender, list.index es una operación O (1). Aquí hay un enlace si quieres saber más. https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

Pruebe este código, le ayudará a obtener su tiempo de ejecución tomado por el operador lis.index.

 import timeit lis=[11,22,33,44,55,66,77] for i in lis: t = timeit.Timer("lis.index(11)", "from main import lis") TimeTaken= t.timeit(number=100000) print (TimeTaken)