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.