PDF de programación - Determinación del k-ésimo mayor de n números

Imágen de pdf Determinación del k-ésimo mayor de n números

Determinación del k-ésimo mayor de n númerosgráfica de visualizaciones

Publicado el 11 de Julio del 2017
606 visualizaciones desde el 11 de Julio del 2017
81,1 KB
5 paginas
Creado hace 15a (03/11/2005)
Determinación del k-ésimo mayor de n números

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (i)

Primera solución : O(n2).

Ordenar decrecientemente los n números. O(n2)
O(1)
Devolver k-ésimo.

1.
2.
función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

Ordenar por inserción ( V[1..n] ); { decrecientemente }
devolver V[k]

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (ii)

Segunda solución : O(k 2 + (n− k)k). Si k = n
1. Ordenar decrecientemente los k 1os números.
2. Para cada número en (k . . . n],
3.
función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

O(k 2)
O((n− k)k)

2 entonces O(n2).

insertar si procede.

O(k)

Ordenar por inserción ( V[1..k] ); { decrecientemente }
para i := k+1 hasta n hacer

j := k;
si V[j] < V[i] entonces

mientras j > 1 y V[j-1] < V[i] hacer

V[j] := V[j-1]; j := j - 1;

fin mientras
V[j] := V[i]

fin para
devolver V[k]

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (iii)

Tercera solución : O(n + k log n). Si k = n

2 entonces O(n log n).

1. Crear un montículo de máximos con los n nos
2. Realizar k − 1 eliminaciones
3. Obtener el mayor

O(n)
O(k(log n))
O(1)

función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

Crear Montículo Máximos ( V[1..n], M );
para i := 1 hasta k-1 hacer

EliminarMax ( M );

fin para
devolver ObtenerMayor ( M );

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (iv)

Cuarta solución : O(k + (n− k) log k). Si k = n
2 entonces O(n log n).
1. Crear montículo de mínimos con los k primeros nos O(k)
O((n− k) log k)
2. Para cada número en (k . . . n],
3.
4.
5.
función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

Determinar si insertar en montículo O(1)

Eliminar mínimo
Insertar nuevo número

O(log k)
O(log k)

Crear Montículo Mínimos ( V[1..k], M );
para i := k+1 hasta n hacer

si ObtenerMenor ( M ) < V[i] entonces

EliminarMin ( M );
Insertar ( V[i], M )

fin para
devolver ObtenerMenor ( M );

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros
  • Links de descarga
http://lwp-l.com/pdf5264

Comentarios de: Determinación del k-ésimo mayor de n números (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad