Complejidad de tiempo de inserción en la lista vinculada

Question

Disculpas Si esta pregunta se siente como una verificación de la solución, pero se solicitó esta pregunta en mi examen de ingreso de posgrado y hay muchas montañas en esto:

¿Cuál es la complejidad del peor de los casos de insertar $ n $ elementos en una lista vinculada vacía, si la lista vinculada debe mantenerse en orden ordenado?

En mi opinión, la respuesta debe ser $ o (n ^ 2) $ porque en cada inserción, tendremos que insertar el elemento en el lugar correcto y Es posible que cada elemento tenga que ser insertado en el último lugar, dándome una complejidad de tiempo de $ 1 + 2 + ... (n-1) + n= o (n ^ 2) $

Sin embargo, la solución que tengo dice que podemos ordenar primero los elementos en $ o (n \ log n) $ y luego, podemos insertarlos uno por uno en $ o (n) $ , dándonos una complejidad general de $ o (n \ log n) $ < / span>.

De la redacción dada de la pregunta, ¿qué solución es más apta? En mi opinión, dado que la pregunta menciona "la lista vinculada debe mantenerse en orden ordenada", me inclino a decir que no podemos ordenar los elementos de antemano y luego insertarlos en el orden ordenado.

Answer 1

La pregunta solo dice que la lista objetivo debe mantenerse en orden ordenado. No dice nada sobre cualquier otra estructura de datos que pueda elegir. La solución propuesta primero hace algún preprocesamiento de los argumentos para insertar, luego hace la inserción correcta. Esto es permitido por la declaración del problema.

Una razón práctica para hacer esto, en lugar de insertar los elementos y luego ordenar, sería si el objeto de la lista vinculada se comparte con otro hilo que requiere que siempre sea ordenado. (En un escenario de este tipo, tendría que asegurarse de que la inserción de un elemento sea atómica). Por lo tanto, esta pregunta no es solo requisitos extraños por ser extraños. Es el tipo de requisitos que surgen a menudo en el mundo real de la programación.

Otra solución con la misma complejidad sería insertar los elementos en la lista de destino a medida que vienen, y mantener un elemento de asignación de elementos de la estructura de datos en paralelo a los punteros de nodo en la lista de destino. Para insertar cada elemento, encuentre el elemento anterior en la asignación, e inserte el nuevo elemento después de este nodo. Esto supone que el proceso de inserción crea los nodos de la lista a medida que va (a diferencia de llenar los nodos en blanco existentes).

Esta pregunta es más sobre la comprensión de lectura que sobre los algoritmos. La forma en que está redactada, es un poco de una pregunta de truco. Es algo mal redactado porque se basa en una lectura precisa, pero no afirma algunos supuestos clave, como el hecho de que obtenga los elementos para insertar costos $ o (n) $ , la comparación de dos elementos se puede realizar en $ o (1) $ , y el dominio de entrada está efectivamente ilimitado (ejercicio: surge con un $ o (n) $ algoritmo Si las entradas son enteros en el rango $ [1,42] $ ). Pero la respuesta dada es correcta.

Hizo la suposición de que no hay forma de usar una estructura de datos auxiliares. Nada en la declaración de problemas prohíbe utilizando estructuras de datos auxiliares. Una forma sencilla de prohibir las estructuras de datos auxiliares sería requerir $ o (1) $ de la memoria superior.

Tenga en cuenta que incluso bajo este supuesto, su razonamiento es incorrecto, o al menos impreciso. Si sabía que los elementos se dan en el orden correcto, puede mantener un puntero a la cola de la lista, y seguir insertando allí, lo que tomaría $ O (n) $ . El peor de los casos no es si todo elemento debe insertarse en la última posición en la lista de destino, pero en la última posición alcanzada al atravesar la lista de alguna manera. El peor de los casos es de hecho $ \ theTa (n ^ 2) $ , pero para demostrar esto, debe demostrar que encontrar el punto de inserción en la lista requiere $ \ THETA (N) $ Time, y esto requiere que demuestre que la distancia desde Any Puntero que tenga en la lista está limitada a continuación por $ \ omega (n) $ . Este es el caso, si tiene un número constante $ a $ de punteros (usted implícitamente asumió $ a= 1 $ , con un solo puntero al inicio de la lista), para que necesite atravesar al menos $ k / a $ nodos después de $ k $ inserciones en el peor de los casos.

Answer 2

La mejor estructura posible que conozco, son los montones de Fibonacci, puede insertar elementos en $ o (1) $ y extraiga el mínimo en $ O (\ log (n)) $ , esto significa que si necesita un orden ordenado de todos los elementos, lo lleva a $ o (n \ log(n)) $ Mientras que la inserción de nuevos elementos solo le cuesta $ o (1) $ , no conozco otra estructura que podría mantenerse al día con esto.

Answer 3

Realmente es una pregunta difícil.En primer lugar, la complejidad de O (NLOGN) se aplica solo a los algoritmos que utilizan la comparación entre sus elementos (algoritmo comparativo).También hay algoritmos que no son comparativos, como el tipo de radix, que su complejidad depende del tamaño en bits que los números deben almacenarse en la memoria.Entonces, si asumimos que podemos ordenar los números de antemano con cualquier algoritmo, entonces también podemos asumir que los números son naturales y el elemento máximo es m <10, por lo que con Radix Ordenaría el peor caso O (10N)= O (norte).Si no podemos hacer ninguna suposición, entonces tienes razón.Si solo se le permite usar listas vinculadas y nada más (sin indexación de ningún tipo), entonces la complejidad es O (n ^ 2) (tipo de burbuja).

Answer 4

Debe ser O (n). Siga el algoritmo como -

1) Si la lista vinculada está vacía, haga el nodo como cabeza y devuélvalo.

2) Si el valor del nodo a insertar es más pequeño que el valor del nodo de la cabeza, luego inserte el nodo Al comienzo y hazla cabeza.

3) En un bucle, encuentre el nodo apropiado después de que se debe insertar el nodo de entrada.

Para encontrar el comienzo adecuado del nodo de la cabeza, sigue moviéndose hasta que alcance un nodo que sea el valor es mayor que El nodo de entrada.El nodo justo antes de eso es el Nodo apropiado

4) Inserte el nodo después del nodo apropiado encontrado en el paso 3