La documentación oficial de CPython detalla la complejidad computacional de las operaciones sobre sus tipos de datos nativos, utilizando la notación Big O para describir cómo crece el tiempo de ejecución según el tamaño de los inputs. Este análisis es crucial para desarrollar software eficiente y predecir el rendimiento en aplicaciones a gran escala.
En el caso de las listas (list), que son secuencias mutables, las operaciones de acceso por índice y longitud tienen una complejidad constante O(1). Sin embargo, insertar o eliminar elementos cerca del inicio requiere desplazar los elementos posteriores, resultando en un coste de O(n-k). Para operaciones frecuentes en ambos extremos, se recomienda el uso de collections.deque. Las tuplas (tuple), al ser inmutables, ofrecen copias en tiempo constante O(1) y no admiten inserciones ni borrados.
Los diccionarios (dict) y conjuntos (set) presentan un comportamiento promedio de O(1) para búsquedas e inserciones, asumiendo una función hash robusta. No obstante, en el peor caso, si todas las claves colisionan, estas operaciones degradan a O(n). Los objetos str y bytes son inmutables, por lo que su copia es trivial (O(1)), mientras que la búsqueda de subcadenas tiene un coste lineal O(n). Finalmente, los objetos range calculan sus elementos bajo demanda, lo que permite que la mayoría de sus operaciones no dependan de la longitud total del rango.