Me pregunto cuál es la complejidad del tiempo del método pop de objetos de lista en Python (en particular en CPython). ¿El valor de N para list.pop (N) también afecta la complejidad?¿Cuál es la complejidad del tiempo para hacer estallar elementos de la lista en Python?
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 en la matriz de punteros.
sí, es O (1) para que aparezca la última elemento de una lista Python, y O (N) para que aparezca un arbitraria elemento (ya que todo el resto de la lista tiene que ser desplazado).
Aquí está un gran artículo sobre cómo se almacenan y manipulan las listas de Python: http://effbot.org/zone/python-list.htm
Entonces, para dejarlo en claro, list.pop (0) es O (n) y list.pop() es O (1). –
Y para obtener ambas operaciones en O (1), use collections.deque vea [aquí] (https://wiki.python.org/moin/TimeComplexity) – galath
La respuesta corta es mirar aquí: https://wiki.python.org/moin/TimeComplexity
Sin argumentos para hacer estallar su junta (1)
Con una argumento para pOP:
tiempo complejidad media:
Cualquier vez que se ponga en una Valora la complejidad de tiempo de esa operación es O (n - k).
Por ejemplo, si usted tiene una lista de 9 artículos de la eliminación de la final de la lista es de 9 operaciones y eliminar desde el comienzo de la lista es 1 Operaciones (borrar el índice 0 ª y en movimiento todo el otra elementos a su índice actual - 1)
Dado que 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)
amortizado Worst Case Complejidad de tiempo
Imagine que tiene una lista de 9 artículos de nuevo.Imagine que está eliminando cada elemento de la lista y ocurre el peor caso y elimina el primer elemento de la lista cada vez.
Dado que la lista se reduce en 1 cada vez que el número de operaciones totales disminuye cada vez de 9 a través de 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, lo hace O (nk)/O (n) que equivale a O (k)
Indicando que es O (n) para el promedio y la complejidad amortizada del peor de los casos es también bastante correcta. Observe que S (k) es aproximadamente O (1/2n) y dejando caer la constante es igual a O (n)
Worst Case Complejidad de tiempo
Estoy de acuerdo con la respuesta dada, pero la explicación es mi humilde opinión equivocada. Puede eliminar cualquier objeto de una lista en el tiempo O (1) (básicamente, hacer que el puntero anterior sea el siguiente y eliminarlo). El problema es que para ENCONTRAR el objeto en esa posición, debe recorrer la lista hasta ese punto punto (toma O (N) tiempo, no se necesita promediar.) Finalmente una nota de caso especial :, pop (0) tomará O (1), no O (0). – ntg
@ntg la lista es una matriz de punteros. para eliminar un puntero de la matriz en el medio, todos los punteros que lo siguen deben moverse hacia arriba en la matriz tomando una cantidad de tiempo proporcional al tamaño de la lista (que denotamos como N), siendo O (N) . Para aclarar el N en la notación de Big-O NO se encuentra el índice del elemento que se devuelve, sino una función que limita el tiempo de ejecución del algoritmo con O (1) siendo tiempo constante, es decir, no depende del tamaño de la lista. O (N) significa que la función de límite es una constante multiplicada por el tamaño de la lista, f (n) = c * n + b. – tvanfosson
Me encuentro corregido :) De hecho, la implementación de la lista es una matriz de punteros. Entonces tu respuesta es correcta. Por pop (N) en tu respuesta te refieres a pop (k), N donde k es la posición del elemento a eliminar, y el tamaño de dicha matriz es N. Entonces k puede variar de 0 a N-1, por lo tanto, por N promedio/2 operaciones para mover los elementos k + 1, ...., N-1 una posición hacia atrás. – ntg