¿Cuál es la complejidad temporal de la función count () de la lista de Python?

Estoy tratando de averiguar cuál es la complejidad temporal de la función count ().

Ej. Si hay una lista de [1, 2, 2, 3] y [1, 2, 2, 3].count(2) se utiliza.

He buscado sin cesar y miré la wiki de Python aquí , pero no está allí.

Lo más cerca que he estado de encontrar una respuesta es aquí , pero el campo de complejidad está vacío. ¿Alguien sabe cuál es la respuesta?

    Adéntrate en el código fuente de CPython y visita Objects/listobject.c , encontrarás el código fuente del método count() allí. Se parece a esto:

     static PyObject * list_count(PyListObject *self, PyObject *value) { Py_ssize_t count = 0; Py_ssize_t i; for (i = 0; i < Py_SIZE(self); i++) { int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ); if (cmp > 0) count++; else if (cmp < 0) return NULL; } return PyLong_FromSsize_t(count); } 

    Lo que hace es simplemente iterar sobre cada PyObject en la lista, y si son iguales en comparación rica (ver PEP 207 ), se incrementa un contador. La función simplemente devuelve este contador.

    Al final, la complejidad del tiempo de list_count es O (n). Solo asegúrese de que sus objetos no tengan funciones __eq__ con grandes complejidades de tiempo y estará seguro.

    Debido a que el método de count tiene que verificar cada entrada en la lista, el tiempo de ejecución será O (n).

    Tiene que visitar todos los elementos para saber si contarlos o no. No hay razón para que haga más trabajo que eso.

    Por lo tanto, no puede ser mejor que O (n), y dado que incluso la implementación más básica, simple y directa es O (n), deberías ser realmente muy estúpido o muy malicioso para hacerlo más lento.

    Ergo, según el sentido común, la complejidad de los pasos en el peor de los casos es la O (n) más probable.