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.

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