23 votos

La extracción de los números 2 n veces y volver a colocar la adición en O(n) en lugar de O(n*log(n))

Estoy presentando un problema con mi profesor se mostró en clase, con mis O(n*log(n)) solución:

Dada una lista de n números nos gustaría realizar la siguiente n-1 veces:

  • Extraer los dos mínimos elementos x,y de la lista y el presente de ellos
  • Crear un nuevo número z , donde z = x+y
  • Poner z de nuevo en la lista

Sugieren una estructura de datos y algoritmos para O(n*log(n)) y O(n)

Solución:

Vamos a utilizar un mínimo de montón:

La creación de la pila una vez solo tendría O(n). Después de eso, la extracción de los dos mínimos elementos tomaría O(log(n)). Colocando z en el montón tomaría O(log(n)).

La realización de la anterior n-1 veces toma O(n*log(n)), ya que:

O(n)+O(n∙(logn+logn ))=O(n)+O(n∙logn )=O(n∙logn )

Pero, ¿cómo puedo hacer en O(n)?

EDITAR:

Diciendo: "extracto de los dos mínimos elementos x,y de la lista y el presente de ellos ", me refiero printf("%d,%d" , x,y), donde x y y son los elementos más pequeños en la lista actual.

12voto

btilly Puntos 14710

Esto no es una respuesta completa. Pero si la lista está ordenada, entonces el problema es easiy factible en O(n). Para hacerlo, organizar todos los números en una lista enlazada. Mantener un puntero a una cabeza, y en algún lugar en el medio. En cada paso, en la parte superior de dos elementos fuera de la cabeza, las imprima, avanzar en la media puntero hasta que es donde la suma debe ir, e insertar la suma.

La inicial del puntero se mueve cerca de 2n veces y el medio puntero se moverá sobre n de veces, con n inserta. Todas estas operaciones son O(1) para el total de la suma es O(n).

En general, usted puede ordenar en el tiempo O(n), pero hay una serie de casos especiales en los que puede. Así, en algunos casos es factible.

El caso general es, por supuesto, no resolubles en tiempo O(n). ¿Por qué no? Porque dada su salida, en el tiempo O(n) puede ejecutar a través de la salida del programa, la construcción de la lista de pares de cantidades con el fin de que vaya, y el filtro de la salida. Lo que queda es el de los elementos de la lista original en orden. Esto daría un O(n) general algoritmo de ordenación.

Actualización: se me pidió para mostrar cómo podría usted salir de la salida (10, 11), (12, 13), (14, 15), (21, 25), (29, 46) a la entrada de la lista? El truco es que siempre mantener todo en orden, entonces usted sabe cómo mirar. Con los enteros positivos, el próximo suma a utilizar siempre estará en el inicio de la lista.

Step 0: Start
  input_list: (empty)
  upcoming sums: (empty)

Step 1: Grab output (10, 11)
  input_list: 10, 11
  upcoming_sums: 21

Step 2: Grab output (12, 13)
  input_list: 10, 11, 12, 13
  upcoming_sums: 21, 25

Step 3: Grab output (14, 15)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sums: 21, 25, 29

Step 4: Grab output (21, 25)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 29, 46

Step 5: Grab output (29, 46)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 75

2voto

cheeken Puntos 9013

Esto no es posible en el caso general.

Su enunciado del problema dice que se debe reducir el conjunto a un único elemento, la realización de un total de n-1 operaciones de reducción. Por lo tanto, el número de operaciones de reducción que se realiza es del orden de O(n). Para lograr un total de tiempo de ejecución de O(n), cada una reducción de la operación debe ejecutarse en O(1).

Se han definido claramente su operación de reducción:

  • quite los 2 un mínimo de elementos de la matriz y de impresión, a continuación,
  • insertar la suma de los elementos en la matriz.

Si la estructura de datos era una lista ordenada, es trivial para quitar un mínimo de dos elementos en O(1) tiempo (pop fuera de la final de la lista). Sin embargo, volver a insertar un elemento en O(1) no es posible (en el caso general). Como SteveJessop señalado, si se puede insertar en una lista ordenada en O(1) vez, la resultante de las operaciones de constituiría una operación O(n) del algoritmo de ordenación. Pero no existe tal algoritmo conocido.

Hay algunas excepciones aquí. Si sus números son enteros, usted puede ser capaz de utilizar "radix insertar" para lograr O(1) se inserta. Si su matriz de números son lo suficientemente disperso en el número de línea, usted puede ser capaz de deducir los puntos de inserción en O(1). Existen numerosas excepciones, pero son las excepciones.

Esta respuesta no responde a su pregunta, de por sí, pero creo que es suficientemente relevante como para justificar una respuesta.

1voto

amit.codename13 Puntos 158

Si el rango de valores es menor que n, entonces esto puede ser resuelto en O(n).

1> Crear una matriz mk de un tamaño igual a la gama de valores y se inicializa a cero

2> recorrer a través de la matriz y el valor de incremento de mk en la posición del elemento de la matriz. yo.e si el elemento de la matriz es un[i] luego de incremento mk [[i]]

3) Para la presentación de las respuestas después de cada uno de los n-1 operaciones de seguir los siguientes pasos:

Hay dos casos:

Caso 1 : todos los de a[i] son positivos

        traverse through mk array from 0 to its size
        cnt = 0
        do this till cnt doesn't equal 2
          grab a nonzero element decrease its value by 1 and increment cnt by 1
        you can get two minimum values in this way
        present them 
        now do mk[sum of two minimum]++

Caso 2 : algunos de a[i] es negativa

        <still to update>

0voto

user1277476 Puntos 1612

O(nlogn) es fácil - sólo tiene que utilizar un montón, treap o skiplist.

O(n) suena difícil.

https://en.wikipedia.org/wiki/Heap_%28data_structure%29
https://en.wikipedia.org/wiki/Treap
https://en.wikipedia.org/wiki/Skip_list

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X