La complejidad del tiempo de la tupla en Python

Hay preguntas similares sobre hash (diccionarios) y listas, también hay una buena información aquí: http://wiki.python.org/moin/TimeComplexity

Pero no encontré nada sobre las tuplas.

El tiempo de acceso para

data_structure[i] 
  • para una lista enlazada es en general O (n)
  • para diccionario es ~ O (1)

¿Qué pasa con la tupla? ¿Es O (n) como para una lista enlazada u O (1) como para una matriz?

    Es O (1) tanto para la lista como para la tupla. Ambos son moralmente equivalentes a una matriz indexada de enteros.

    Las listas y las tuplas se pueden indexar exactamente de la misma manera que los arreglos están en otros idiomas.

    Una explicación simplificada es que el espacio se asigna para referencias a objetos, esas referencias ocupan una cantidad uniforme de espacio y cualquier índice se multiplica simplemente por el tamaño de la referencia para obtener un desplazamiento en la matriz. Esto da constante, O (1), acceso para listas y tuplas.

    Obtener un elemento de una lista enlazada es O (n), pero las listas de Python tienen implementaciones basadas en matrices, por lo que el costo es O (1).

    Las tuplas también se implementan utilizando matrices, por lo que es O (1) para ellas también.

    Debería ser O(1) , porque en realidad es solo una lista.

    Pero para las listas de python, ¡esperaría que O(1) también! Es posible que desee volver a pensarlo …