secuencial - ¿Cuál es la complejidad del tiempo para hacer estallar elementos de la lista en Python?
busqueda secuencial ventajas y desventajas (3)
Pop() para el último elemento debe ser O (1) ya que solo necesita devolver el elemento al que hace referencia el último elemento de la matriz y actualizar el índice del último elemento. Esperaría que pop() para un elemento arbitrario sea O (N) y requiera en promedio N / 2 operaciones ya que necesitaría mover cualquier elemento más allá del elemento que está eliminando una posición hacia arriba en la matriz de punteros.
Me pregunto cuál es la complejidad del tiempo del método pop de objetos de lista en Python (en CPython en particular). ¿El valor de N para list.pop (N) también afecta la complejidad?
Sí, es O (1) para mostrar el último elemento de una lista de Python, y O (N) para mostrar un elemento arbitrario (ya que todo el resto de la lista debe desplazarse).
Aquí hay un excelente artículo sobre cómo se almacenan y manipulan las listas de Python: http://effbot.org/zone/python-list.htm
La respuesta corta es mira aquí: https://wiki.python.org/moin/TimeComplexity
Sin argumentos para mostrar su O (1)
Con un argumento para explotar:
- Tiempo promedio Complejidad O (k) (k representa el número pasado como argumento para el pop
- Amortización de la complejidad del tiempo del peor caso O (k)
- La peor complejidad de tiempo de caso O (n)
Complejidad de tiempo promedio:
Cada vez que ingresa un valor, la complejidad del tiempo de esa operación es O (n - k).
Por ejemplo, si tiene una lista de 9 elementos que eliminar desde el final de la lista hay 9 operaciones y la eliminación desde el comienzo de la lista es 1 operaciones (eliminando el 0 ° índice y moviendo todos los demás elementos a su índice actual - 1 )
Como n - k para el elemento medio de una lista es k operaciones, el promedio puede acortarse a O (k).
Otra forma de pensar sobre esto es imaginar que cada índice fue eliminado de su lista de 9 elementos una vez. Eso sería un total de 45 operaciones. (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)
45 es igual a O (nk) y dado que la operación pop ocurrió O (n) veces se divide nk por n para obtener O (k)
Amortizó la peor complejidad de tiempo de caso
Imagine que tiene una lista de 9 elementos nuevamente. Imagine que está eliminando cada elemento de la lista y ocurre el peor caso y elimina el primer elemento de la lista cada vez.
Como la lista se reduce en 1 cada vez, el número de operaciones totales disminuye cada vez desde 9 hasta 1.
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45. 45 es igual a O (nk). Dado que hizo 9 operaciones y 9 es O (n) para calcular el escenario del peor caso amortizado, usted hace O (nk) / O (n) que es igual a O (k)
Declarar que es O (n) para el promedio y la peor complejidad del tiempo de caso amortizado también es algo así como correcto. Observe que O (k) es aproximadamente O (1 / 2n) y que la constante es igual a O (n)
La peor complejidad de tiempo de caso
- A diferencia de la peor amortización de la complejidad del tiempo de caso, no se toma en cuenta el estado de la estructura de datos y solo se piensa en el peor caso para una operación individual.
- En ese caso, el peor caso es que debe eliminar el primer elemento de la lista que es O (n) hora.