Desarrollo de Python
  1. Desarrollo de Python
  3. ¿Cuál es la complejidad temporal de la función count () de la lista de Python?
Intereting Posts
Django – No hay módulo llamado PIL ¿Cómo lidiar con los valores xmlns al analizar un archivo XML? ¿Por qué on_message deja de funcionar los comandos? ¿Cuál es una buena manera de obtener una medida de similitud de dos imágenes que contienen un gráfico de líneas? ¿Cómo funciona la llamada en Python? Rebanado dynamic numpy por fila Decidir e implementar un algoritmo de tendencias en Django. Múltiples declaraciones if en una función lambda ¿Cómo pasar varios valores para un solo parámetro de URL? Un progtwig de Python no se ejecuta en el texto sublime 3, pero el éxito en bash Cuándo usar multiindexing vs. xarray en pandas Python: directorio del script Pérdida de memoria en la biblioteca ndb de Google Salida extra ninguna al imprimir un argumento de línea de comando Un error para generar un archivo exe usando pyinstaller – typeerror: str esperado, bytes u os.PathLike objeto, no NoneType

¿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.